# 038. Count-and-Say

difficulty: Easy

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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 groups so that each group is a contiguous section all of the **same character.** Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

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

![](https://assets.leetcode.com/uploads/2020/10/23/countandsay.jpg)

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

&#x20;

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

&#x20;

**Constraints:**

* `1 <= n <= 30`

## Method One

这个题麻烦在于弄懂题意。看起来好像可以递归，实际上不太能。 其实就是重复 n - 1 次 **把一个函数的输出当成下一次的输入**。 而这个函数本身干了什么事，虽然是这个题目中比较重要的部分，但是却是这个题中得到的最不重要的知识。 我觉得这个题目考察的最重要的就是，**能写出下面这种去耦的代码**。

```
class Solution {
    public String countAndSay(int n) {
        if( n == 1){
            return "1";
        }
        String val = "1"; 
        for(int i = 1; i < n; i++){
            val = getNextVal(val);
        }
        return val;
    }
    
    public String getNextVal(String val){
        StringBuilder sb = new StringBuilder();
        char[] input = val.toCharArray();
        char cur = input[0];
        int count = 0;
        for(char c : input){
            if( cur != c ){
                sb.append(String.valueOf(count)).append(cur);
                cur = c;
                count = 1;
            }else{
                count++;
            }  
        }
        sb.append(String.valueOf(count)).append(cur);
        return sb.toString();
    }
}
​
```
