The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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, generate the nth sequence.
- The sequence of integers will be represented as a string.
Python Solution:
class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n < 1: return "";
def next(s):
res = []
i, j = 0, 1
while j < len(s):
if s[j] == s[i]:
j += 1
continue
res.extend(str(j - i))
res.extend(s[i])
i = j
j = i + 1
res.extend(str(j - i))
res.extend(s[i])
return res
s = ['1']
for _ in range(n - 1):
s = next(s)
return "".join(s);
Summary:
- Remember the next.
LeetCode: 38. Count and Say
近期评论