38. Count and Say

ゝ一纸荒年。 2022-03-07 11:38 235阅读 0赞

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
    2.     11
    3.     21
    4.     1211
    5.     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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:
    Input: 1
    Output: "1"
    
    Example 2:
    Input: 4
    Output: "1211"

难度：easy

题目：  
count-and-say 序列如下如示：

1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221
    1 读作1个1或11
    11 读作2个1或21
    21 读作1个2，接着1个1 或1211

给定一个整数n 大于等于1小于等于30, 产生第n组序列。  
注意：每项由整数组成的序列以字符串表示。

Runtime: 3 ms, faster than 72.13% of Java online submissions for Count and Say.  
Memory Usage: 25.8 MB, less than 98.33% of Java online submissions for Count and Say.

class Solution {
        public String countAndSay(int n) {
            String str = "";
            for (int i = 0; i < n; i++) {
                str = generateNext(str);
            }
            
            return str;
        }
        
        private String generateNext(String s) {
            if (s.isEmpty()) {
                return "1";
            }
            // add and end flag
            s += ".";
            int counter = 1;
            StringBuilder str = new StringBuilder();
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) != s.charAt(i - 1)) {
                    str.append(counter).append(s.charAt(i - 1));
                    counter = 1;
                } else {
                    counter++;
                }
            }
            
            return str.toString();
        }
    }