Count and Say

这题是Leetcode第38题，难度为easy。

Question

This is the question.

Answer

Solution 1

I first to solve this problem iteratively with the help of function Say. While I do use stack to check the consective equal numbers and lower the space complexity.

class Solution:
    def countAndSay(self, n: int) -> str:
        
        def say(s):
            result = ''
            stack = []
            for i in s:
                if stack == []:
                    stack.append(i)
                else:
                    if i != stack[-1]:
                        num = len(stack)
                        result = result + str(num) + stack.pop()
                        stack = []
                        stack.append(i)
                    else:
                        stack.append(i)
            result = result + str(len(stack)) + stack[0]
            return result
            
        
        def helper(n):
            t = 1
            while t <= n:
                if t == 1:
                    output = '1'
                    t = t + 1
                else:
                    output = say(output)
                    t = t + 1
            return output
                
        
        return helper(n)

Function Say take a string s as input and return a say output, which is also a string. While in function helper, we take the output of n-1 as input to n, and do it iteratively. The total time complexity is $O(n \times length(s))$.

Solution 2

We can use recursion to solve this problem.
Base condition:

$$if \quad n =1, \quad return \quad '1'$$

State change:

$$f(n) = say[f(n-1)]$$

The code lists as following:

class Solution:
    def countAndSay(self, n: int) -> str:
        
        def say(s):
            result = ''
            stack = []
            for i in s:
                if stack == []:
                    stack.append(i)
                else:
                    if i != stack[-1]:
                        num = len(stack)
                        result = result + str(num) + stack.pop()
                        stack = []
                        stack.append(i)
                    else:
                        stack.append(i)
            result = result + str(len(stack)) + stack[0]
            return result
            
        
        def helper(n):
            if n == 1:
                return '1'
            else:
                return say(helper(n-1))
                

        return helper(n)

Conclusion

Both solutions have quick running time and small memory usage.
Runtime: 32 ms, faster than 74.21% of Python3 online submissions for Count and Say.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Count and Say.