Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

Naive Way: 很有趣的题目。第一次写就成功了，看来是一道简单的题目。通过读取上一次的String生成当前的String。

public class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for(int i = 2;i <= n;i++){
            int j = 0;
            String newStr = "";
            while(j < str.length()){
                int count = 1;
                while(j+count < str.length()){
                    if(str.charAt(j)!=str.charAt(j+count))
                        break;
                    count++;
                }
                newStr += (char)(count+'0');
                newStr += str.charAt(j);
                j += count;
            }
            str = newStr;
        }
        return str;
    }
}

Improved Way: Discuss里有用recursive写的，感觉会更舒服些。