[LeetCode Road] Count and Say - Solution/C++

38. Count and Say

Question:

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 n^th term of the count-and-say sequence.

Example:

Input: n = 1
Output: "1"
Explanation: This is the base case.

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"

Constraints:

1 <= n <= 30

Source code

Version 1

Idea:
It is a sticky problem for me, my methods always got Time Limit Exceeded. I had no choice but to refer to Huahua's Tech Road.

Declare a string consists 1 character, if n = 1, return a string. record as a index, it starts from 0. We must check res[record] != res[j], use j - count we can get number of the same characters. Finally, use temporary string to store the results.

class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        for(int i = 1; i < n; i++){
            string temp = "";
            int record = 0, len = res.length();
            for(int j = 0; j < len; j++){
                if(res[record] != res[j] || j == len){
                    int count = j - record;
                    temp += '0' + count;
                    temp += res[record];
                    record = j;
                }
            }
            res = temp;
        }
        return res;
    }
};