[LeetCode] 38. Count and Say

Posted on | In

Problem

The count-and-say sequence is the sequence of integers with the first five terms as following:

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

1
2
Input: 1
Output: "1"

1
2
Input: 4
Output: "1211"

Explanation 1

  1. We initialize the res to 1 first, then if n is 2, we need to do 1 transformation; if n is 3, we need to do 2 tranformation.

  2. During each transformation, we have a varialbe temp to keep track of the temporary result. After the tranformation, we update res to the transformation result; when we finish the loop, we return the res string.

  3. In each transformation, start pointing from the first character of res, compare it with the next character, if they are the same, then update count and move the pointer to the next character and repeat the process, until the current character to the end because there is no next character to compare, or until the current character is not the same as the next character. We append the count and the current character to the res. Before we compare, we set the count back to 1.

  4. Finally return res as string.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";

        StringBuilder temp = new StringBuilder();
        StringBuilder res = new StringBuilder("1");

        while (--n > 0) {
            for (int i = 0; i < res.length(); i++) {
                int count = 1;
                while (i+1 < res.length() && res.charAt(i) == res.charAt(i+1)) {
                    i++;
                    count++;
                }
                temp.append(count);
                temp.append(res.charAt(i));
            }
            res.setLength(0);
            res.append(temp);
            temp.setLength(0);
        }
        return res.toString();
    }
}

Explanation 2

  1. We can also use recursion to solve this problem. The base case for the main function is if the input number is 1, then we return string "1" immediately. Then we pass n-1 to the main function to get the previous number’s result string previous. For input n, we can get the result by just count and say the string previous.

  2. Loop through the string previous using index i. Inside the loop, we create another variable j = i + 1, and we use previous[j] to look behind comparing with previous[i]. While previous[j] == previous[i], we increase j. Outside the while loop, we can calculate the count is j - i, the number we say is previous[i]. We append the count and say to the result string, then update i = j.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";
        String previous = countAndSay(n-1);
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < previous.length();) {
            int j = i + 1;
            while (j < previous.length() && previous.charAt(i) == previous.charAt(j)) {
                j += 1;
            }
            res.append(j - i);
            res.append(previous.charAt(i));
            i = j;
        }
        return res.toString();
    }
}