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

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

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();
    }
}
​