Count and Say

update Jan 19, 2018 16:46

LeetCode

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, 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:

    Input: 1
    Output: "1"

Example 2:

    Input: 4
    Output: "1211"

Basic Idea:

解法就是按照之前一次的结果，从左到右数相同元素的个数，生成新的结果，再往复继续。具体地，每次的结果存储在一个 StringBuilder 中，例如当前结果为 1121，从左到右计算每个char的个数，我们发现有两个1，则将 21 append 到 newSB 中，再继续往后。

• Java Code:

  class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1"; // corner case
        StringBuilder sb = new StringBuilder();
        sb.append("1"); // initialize
  
        // "1" is the 1st one (0), so start from 2nd (1).
        for (int i = 1; i < n; ++i) {
            StringBuilder newSb = new StringBuilder(); // new result stored here
            int curr = 0; // pointer keep going right
            while (curr < sb.length()) {
                int count = 0;
                char c = sb.charAt(curr);
                while (curr < sb.length() && sb.charAt(curr) == c) {
                    count++;
                    curr++;
                }
                newSb.append(String.valueOf(count));
                newSb.append(c);
            }
            sb = newSb;
        }
        return sb.toString();
    }
  }
  

update May 4, 2018 0:58

C++ Code:

感觉之前写的Java版本的思路更好理解。注意，c++中将char c转为string可以用 string(1, c);

    class Solution {
    public:
        string countAndSay(int n) {
            string last{"1"};
            // 运行 n-1 次
            for (int i = 1; i < n; ++i) {
                string curr;
                char prev = last[0];
                int count = 1;
                // 数之前string每个数字的个数，生成curr string
                for (int j = 1; j < last.size(); ++j) {
                    if (last[j] == prev) {
                        count++;
                    } else {
                        curr.append(to_string(count) + prev);
                        prev = last[j];
                        count = 1;
                    }
                }
                curr.append(to_string(count) + prev);
                last = curr;
            }
            return last;
        }
    };