動機
這題的題目敘述真的不太好,夢回接手新任務,霧裡看花,用力撞牆的感覺
Problem
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 fromcountAndSay(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 groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
For example, the saying and conversion for digit string 3322251
:
Given a positive integer n
, return the nth
term of the count-and-say sequence.
Example 1:
Input: n = 1Output: 1Explanation: This is the base case.
Example 2:
Input: n = 4Output: 1211Explanation:countAndSay(1) = 1countAndSay(2) = say 1 = one 1 = 11countAndSay(3) = say 11 = two 1's = 21countAndSay(4) = say 21 = one 2 + one 1 = 12 + 11 = 1211
Constraints:
1 <= n <= 30
Sol
就是看string中的數字直到變成鱉的數字之前,
- 有幾個
- 是什麼數字
最後放到string中
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
else:
s = self.countAndSay(n-1)
chars = []
for c in s:
if not chars or chars[-1][0] != c:
chars.append([c,1])
else:
chars[-1][1] += 1
ret = []
for p in chars:
ret += [str(p[1]), p[0]]
return ''.join(ret)