Let’s solve a medium problem together on Leetcode.com: Count and Say
Description
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 thenth
term of the count-and-say sequence.
Example:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
Solution
For a given string, in order to “Count and Say” it, there are two variables to consider:
- count of the current character
- what’s the current character?
Assume the string we’re visiting is “1211”, let’s have two variables count
and previous
to record the result while iterating the string.
- Step 1: initialization
Before visiting the string, let’s say count = 0
and previous = ‘.’
to represent the initial state and a variable result
to denote the output.
- Step 2: visit index 0, character = ‘1’
Now, the current character we’re visiting is ‘1’. prevous = ‘.’
is denoting the current character is the beginning of the string, we simply increment the count
by 1 and set the previous = ‘1’
for the next visiting character.
- Step 3: visit index 1, character = ‘2’
The current character we’re visiting is ‘2’. prevous = ‘1’
is denoting the current character is a new character we need to “count and say”. Now, we need to do two things: 1). record the previous result: append count
and previous
to the result. After appending, result = ‘11’
; 2). renew count = 1
, and prevous = ‘2’
for the next visiting character.
- Step 4: visit index 2, character = ‘1’
The current character we’re visiting is ‘1’. prevous = ‘2’
is denoting the current character is a new character we need to “count and say”. Now, we need to do two things: 1). record the previous result: append count
and previous
to the result. After appending, result = ‘1112’
; 2). renew count = 1
, and prevous = ‘1’
for the next visiting character.
- Step 5: visit index 3, character = ‘1’
The current character we’re visiting is ‘1’ is the same with prevous = ‘1’
. We increment the count = 2
variable and leave the previous
.
- Step 6: done iteration
After iterating the string, we still need to append the last visiting's result to the output: result = ‘111221’
. Depending on the iteration times, we’ll decide whether return the result
or input it as a string for the next iteration.
Code
def countAndSay(n: int) -> str:
res = '1' for _ in range(1, n):
prev, count = '.', 0
curr_str = ""
for char in res:
if char == prev or prev == '.':
count += 1
else:
curr_str += str(count) + prev
count = 1
prev = char curr_str += str(count) + prev
res = curr_str return res