Leetcode 38: Count and Say

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 from countAndSay(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 the nth term of the count-and-say sequence.

Example:

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

Reference

on the way to become a programmer