I've worked on a problem for a long time. It turns out to be a simple problem ..

Title Description

Address ： Appearance array
The meaning of the topic is easy to understand , It's a recursive process , from ‘1’ Start , Make a description of each input string in several formats , Then take this description as the next input , Until the second n The result of item .

Solution 1

This problem is an obvious recursive problem , But because I'm not good at recursion , So consider how to do it directly without recursion . So let's briefly say what I think . My approach is to write a function that divides and describes the input string first , Then call this function repeatedly . So the focus of this method is how to write the function of string division and description .

class Solution:
    def countAndSay(self, n: int) -> str:
        if n ==1:
            return '1'
        res = self.countandsay('1')
        for i in range(2,n):
            t = self.countandsay(res)
            res = t
        return res

    def countandsay(self, s: str) -> str:
        res = []
        count = 1
        pres = s[0]
        i, n = 1, len(s)
        if n == 1:
            res.append('1')
            res.append(str(s[0]))
            return ''.join(res)
        while i < n:
            if pres == s[i]:
                count = count + 1
                i = i+1
            else:
                res.append(str(count))
                res.append(str(pres))
                pres = s[i]
                count = 0
        if count > 0:
            res.append(str(count))
            res.append(str(s[n-1]))
        return "".join(res)

Find the description of the string and directly traverse the string , Compare whether each character is the same as the previous character and count , Then save the characters traversed each time and the number of occurrences in the array , Finally, convert the array into a string and return .

recursive + Double pointer

Methods from the comments area , I feel that this is the thing to be tested in this question .

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return '1'
        s = self.countAndSay(n - 1)
        
        ans = ''
        start, end = 0, 0
        while end < len(s):
            while end < len(s) and s[start] == s[end]:
                end += 1
            ans += str(end - start) + s[start]
            start = end

        return ans

 author ： Like Ye Zi's Wang 
 link ：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnpvdm/?discussion=sKH5WT
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Recursion still needs to be learned