題目:

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

countAndSay(1) = "1"
countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

有一系列字串以以下規則制定:
第一項為"1"
第二項表示第一項為1個1,第二項為"11"
第三項表示第二項為2個1,第三項為"21"
第四項表示第三項為1個2,1個1,第四項為"1211"
第五項表示第四項為1個1,1個2,2個1,第五項為"111221"
以此類推
而題目給定一數n,我們要回傳這系列字串的第n項

為此我們設置一個遞迴函數x

class Solution:
    def countAndSay(self, n: int) -> str:
        def x(a,n,s):
            if n==a:
                return s
            
            news=""
            temp=""
            for i in s:
                if temp=="" or temp[0]==i:
                    temp=temp+i
                else:
                    news=news+str(len(temp))+temp[0]
                    temp=i
                    
            news=news+str(len(temp))+temp[0]
            temp=""
                
                
            return x(a+1,n,news)
        
        return x(1,n,"1")

a表示現在在第幾項,n表示我們要回傳第幾項,s表示第a項的字串
若a等於n,代表s就是我們要的字串,回傳s

反之,我們則要開始製作下一項字串
我們先從頭開始遍歷s
若都遇到一樣的字元則不斷填入temp
遇到不一樣的字元則在news後加上str(len(temp))+temp[0]
temp改為新字元
像是"21"就會分割為"12"和"11"兩個部分,結合為"1211"
接著往下執行x(a+1,n,news)

回傳x(1,n,"1")
最後執行時間51ms(faster than 87.76%)

那我們下題見