# 38. Count and Say

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 substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string `"3322251"`:

Given a positive integer `n`, return the`nth` term of the count-and-say sequence.

Example 1:

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

Example 2:

``````**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`

``````class Solution {
public:
string countAndSay(int n) {
string res = "1";
while (--n) {
string cur;
for (int i = 0; i < res.size(); ++i) {
int cnt = 1;
while (i + 1 < res.size() && res[i] == res[i + 1]) {
++cnt;
++i;
}
cur += to_string(cnt) + res[i];
}
res = cur;
}
return res;
}
};
``````

``````1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
3 1 1 3 1 1 2 2 2 1 2 3 2 1 1 2 1 1 1 3 1 2 2 1 1 3 1 2 1 1 3 2 1 1
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/38

Encode and Decode Strings

String Compression

https://leetcode.com/problems/count-and-say/

https://leetcode.com/problems/count-and-say/discuss/16000/Show-an-Answer-in-Java

https://leetcode.com/problems/count-and-say/discuss/16043/C%2B%2B-solution-easy-understand

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation