【LeetCode刷题】--38.外观数列

38.外观数列

方法：遍历生成

该题本质上是依次统计字符串中连续相同字符的个数

例如字符串 1112234445666我们依次统计连续相同字符的个数为: 3 个连续的字符 1, 222 个连续的 2，1 个连续的字符 3，3个连续的字符 4，1个连续的字符 5，3个连续的字符 6。我们对其进行整理为 (3)1(2)2(1)3(3)4(1)5(3)6，我们将括号内的数字也转换为字符串为 312213341536。

算法：

题目中给定的递归公式定义的数字字符串序列如下：

countAndSay(1)：“1”；
countAndSay(n)：是对countAndSay(n-1)的描述，然后转换成另一个数字字符串

定义字符串Si表示countAndSay(i)，如果要求得Sn，需要先求出Sn-1，然后按照上述描述的方法生成，即从左到右依次扫描字符串Sn-1中连续相同的字符的最大数目，然后将字符的统计数目转化为数字字符串再连接上对应的字符

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for(int i = 2; i<=n;i++){
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;
            while(pos < str.length()){
                while(pos < str.length() && str.charAt(pos) == str.charAt(start)){
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            } 
            str = sb.toString();
        }
        return str;

    }
}