38. Count and Say
String, AMateList ·Problem Statement
link: LeetCode.cn LeetCode The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
countAndSay(1) = “1” countAndSay(n) is the run-length encoding of countAndSay(n - 1). Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string “3322251” we replace “33” with “23”, replace “222” with “32”, replace “5” with “15” and replace “1” with “11”. Thus the compressed string becomes “23321511”.
Given a positive integer n, return the nth element of the count-and-say sequence.
Example:
Input: n = 4
Output: "1211"
Input: n = 1
Output: "1"
Constraints:
1 <= n <= 30
Follow up: Could you solve it iteratively?
Solution Approach
The solution iteratively generates each term in the count-and-say sequence by using run-length encoding of the previous term until reaching the nth term.
Algorithm
-
Initialize and Iterate: Start with the initial term “1” and iterate n - 1 times to build up to the nth term.
-
Run-Length Encoding: For each iteration, construct the new term by counting consecutive identical characters in the current term and appending the count followed by the character to the new term.
-
Update Term: After processing the current term, update it to the newly constructed term and repeat the process until the desired term is reached.
Implement
class Solution:
def countAndSay(self, n: int) -> str:
prev = "1"
for i in range(n - 1):
curr = ""
start = 0
pos = 0
while pos < len(prev):
while pos < len(prev) and prev[pos] == prev[start]:
pos += 1
curr += str(pos - start) + prev[start]
start = pos
prev = curr
return prev