Look and Say Term
Problem
The look-and-say sequence starts with "1". Each later term is made by reading the previous term aloud in runs of equal digits: "1" is one 1, giving "11"; "11" is two 1s, giving "21"; "21" is one 2 then one 1, giving "1211". Given n of at least 1, return the n-th term as a string.
Examples
Input: n = 4
Output: "1211"Input: n = 5
Output: "111221"
Why: "1211" reads as one 1, one 2, two 1sInput: n = 1
Output: "1"
Why: edge case, the first term is given, nothing to describeHints
0 / 3
The n-th term is defined entirely in terms of the term before it. That is exactly the shape of a recursive definition.
The base case is n equal to 1. For any larger n, first get term n minus 1, then describe it.
To describe a string, walk it in runs: from the start of a run, move forward while the digit stays the same, then write the length of the run followed by the digit, and continue from where the run ended.
Solution
The definition is already recursive: term 1 is "1", and term n is the description of term n minus 1. Describing a string means splitting it into runs of equal digits and writing each run as its length followed by the digit, which one pass with two indices does. The recursion is n levels deep, which is fine for the small n this sequence is used with, since the terms grow by roughly a third at every step. Time and space are proportional to the total length of the terms produced, dominated by the length of the n-th term.
def look_and_say(n):
if n == 1:
return "1" # base case
prev, out, i = look_and_say(n - 1), [], 0
while i < len(prev):
j = i
while j < len(prev) and prev[j] == prev[i]:
j += 1 # extend the run of prev[i]
out.append(str(j - i) + prev[i]) # count, then digit
i = j
return "".join(out)
print(look_and_say(4)) # -> 1211
print(look_and_say(5)) # -> 111221
print(look_and_say(1)) # -> 1
print(look_and_say(8)) # -> 1113213211Stuck on the idea rather than the code? Recursion Basics covers it.