38. Count and Say

【Description】
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.

【Idea】

这个问题我读了好久没明白~~~
后来Google了一下，才知道是一个字符的 count+string拼接
1：1
2：11 （1中有1个1）
3：21（2中有2个1）
4：1211（3中有1个2和1个1）
所以肯定是递归，时间复杂度：O(N), submission特别慢， 还在找原因
看了别的童鞋的code，也可以直接用正则做，但我想写下base

核心代码在拿到上一个数字的字符之后的统计操作

【Solution】

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        else:
            prev = self.countAndSay(n-1)
            # print('current n :{}, prev:{}'.format(n, prev))
            ret = ''
            i = 0
            while i < len(prev): 
                temp = prev[i]
                cnt = 0
                bond = i+1    #   规定当前相等字符的右边界
                while bond < len(prev) and prev[bond] == prev[i]:
                    bond += 1
                cnt = bond - i
                ret += str(cnt) + temp
                i = bond
            # print('to return string:{}'.format(ret))
            return ret