The count-and-say sequence starts with "1". Each next term is made by reading the previous term aloud in groups of equal digits: for every group, write how many digits it has followed by the digit. For example, "3322251" is read as two 3s, three 2s, one 5, one 1, giving "23321511". Given n, return the n-th term.
"1", "11" (one 1), "21" (two 1s), "1211" (one 2, one 1).- 1 <= n <= 30
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A recursive definition is easy to write but just repeats the same work; an iterative loop is clearer. Start from "1" and apply the "read aloud" step n - 1 times. Each step is a run-length encoding: scan once, and for each run of the same digit, write its length and the digit. Use a string builder so each step is linear in the length of the term.
Algorithm
- Set
cur = "1". - Repeat
n - 1times: scancurwith indexi. - Let
jmove right whilecur[j] == cur[i]; appendj - iandcur[i]to a builder, then seti = j. - Replace
curwith the built string. - Return
cur.
O(n * L), where L is the length of the longest termSpace: O(L)class Solution: def countAndSay(self, n: int) -> str: cur = "1" for _ in range(n - 1): out = [] i = 0 while i < len(cur): j = i while j < len(cur) and cur[j] == cur[i]: j += 1 # end of run out.append(str(j - i)) # count out.append(cur[i]) # digit i = j cur = "".join(out) return cur