博文中会简要介绍Leetcode P0038题目分析及解题思路。

“Count and Say”是一道比较简单的题目，题目描述其实不是很清晰，大致是说一开始有个1，然后下次一边数一边说，即“有一个1”，即“one 1”也就是“11”，然后下一次说“有两个1”，即“two one(s)”也就是“21”，以此类推。

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

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. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

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

以下是C++的题解代码实现。

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1)
            return "1";
        
        string last_row = "1#";
        string curr_row = "";
        for (int idx=2; idx<=n; ++idx) {
            int length = last_row.length();
            curr_row = "";
            int count = 1;
            for (int itr=0; itr<length-1; ++itr){
                if (last_row[itr] == last_row[itr+1])
                    ++count;
                else {
                    curr_row += to_string(count)+last_row[itr];
                    count = 1;
                }
            }
            
            last_row = curr_row+"#";
        }
        return curr_row;
    }
};