leetcode with python:38. Count and Say

题目:

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%)

那我们下题见