> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/38.-count-and-say.md).

# 38. Count and Say

## 1.問題

![](/files/-LS2I0ZyEdF5_0YD-BZ4)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 時間複雜度與可用空間是否有限制?&#x20;
  * n是否會 <= 0?
* function header, parameter
* test input
* 說明想法
  * 觀察規律
  * 可以用遞迴的方式求解
    * n == 1時, 返回"1"
    * n != 1時, 是觀察前一個string的字母而組成
    * 因此等到反彈的字串返回時, 進行count and say &#x20;
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
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];
    }
};
```