Tuesday, July 22, 2014

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 nth sequence.

Note: The sequence of integers will be represented as a string.

根据题目的意思进行递归操作,递归N次。有时候在整个循环结束时,记得检查下,最后一些case有没有加进结果里。
public class Solution {
    public String countAndSay(int n) {
        if (n < 1) {
            return "";
        }
        
        return countHelp("1", n - 1);
    }
    
    private String countHelp(String s, int num) {
        if (num == 0) {
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        char cur = s.charAt(0);
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (cur == s.charAt(i)) {
                count++;
            } else {
                res.append(count);
                res.append(cur);
                cur = s.charAt(i);
                count = 1;
            }
        }
        res.append(count);
        res.append(cur);
        return countHelp(res.toString(), num - 1);
    }
}

No comments:

Post a Comment