38. Count and Say

1.問題

2.想法

• 提問

  • 時間複雜度與可用空間是否有限制?

  • n是否會 <= 0?

• function header, parameter

• test input

• 說明想法

  • 觀察規律

  • 可以用遞迴的方式求解

    • n == 1時, 返回"1"

    • n != 1時, 是觀察前一個string的字母而組成

    • 因此等到反彈的字串返回時, 進行count and say

• 測試計算複雜度

3.程式碼

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        } 
        
        string newStr = countAndSay(n - 1);
        string res = "";
        int index = 0, cnt = 1, tmp = 0;
        int size = newStr.length();
        while (index < size - 1) {
           if (newStr[index] != newStr[index + 1]) {
               res.push_back(char(cnt + '0'));
               res.push_back(newStr[index]);
               cnt = 1;
           } else {
               cnt++;
           }
           index++;
        }
        res.push_back(char(cnt + '0'));
        res.push_back(newStr[index]);
            
        return res;
    }
};

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            s = getString(s);
        }
        return s;
    }
private:
    string getString(string s) {
        string res = "";
        int count = 1;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s[i] != s[i + 1]) {
                res.push_back(char(count + '0'));
                res.push_back(s[i]);
                count = 1;
            } else {
                ++count;
            }
        }
        res.push_back(char(count + '0'));
        res.push_back(s[s.length() - 1]);
        
        return res;
    }
};

class Solution {
public:
    string countAndSay(int n) {
        vector<string> cache(n, "");
        return count(n, cache);
    }
private:
    string count(int n, vector<string>& cache) {
        if (n == 1) {
            return "1";
        } else if (n == 2) {
            return "11";
        }
        if (cache[n - 1] == "") {
            string s = count(n - 1, cache);
            string res = "";
            char tmp = s[0];
            int cnt = 1;
            for (int i = 1; i < s.length(); i++) {
                if (s[i] == tmp) {
                    cnt++;
                } else {
                    res = res + to_string(cnt);
                    res.push_back(tmp);
                    tmp = s[i];
                    cnt = 1;
                }
            }
            res = res + to_string(cnt);
            res.push_back(tmp);
            cache[n - 1] = res;
        }
        return cache[n - 1];
    }
};