[LeetCode] 038. Count and Say

• Problem (Easy)
• Approach 1: (My Solution)
  • Idea
  • Solution
  • Complexity

Problem (Easy)

038. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221 1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

• Input: 1
• Output: “1”

Example 2:

• Input: 4
• Output: “1211”

Approach 1: (My Solution)

Idea

Write a recursion generator to “say” the previous string. Then, set the first item and loop calling the generator n-1 time.

Solution

        def say(s):
            counter = 0 
            tmp = s[0]
            res = ''
            for c in s:
                if c == tmp:
                    counter += 1
                else:
                    res += str(counter) + tmp 
                    tmp = c 
                    counter = 1 
            res += str(counter) + tmp 
            return res 
    
        res = '1'
        for i in range(n-1):
            res = say(res)
        return res 

Complexity

• Time: $O(n)$?
• Space: $O(n)$?

KF