38. Count and Say Leetcode Java

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.

Solution:

This is a classic algorithm problem. No fancy algorithm, all about String processing.

Basic idea is using a string buffer to store last generated string and process it char by char. Check if the current char is the same as the next char, if yes, increment the counter, else increment the counter and output the counter and the current char to the result string buffer, and reset the counter. 

Time complexity: O(m*n) m is the string length. 

 public String countAndSay(int n) {  
    if(n==0) return "";  
    if(n==1) return "1";  
    String pre="1";  
    for(int i=2; i<=n;i++){  
      StringBuilder cur=new StringBuilder();  
      int count=0;  
      for(int j=0;j<pre.length();j++){  
          count++;  
          if(j==pre.length()-1 || pre.charAt(j)!=pre.charAt(j+1)) {  
            cur.append(count);  
            cur.append(pre.charAt(j));  
            count=0;  
          }  
      }  
      pre=cur.toString();  
    }  
    return pre;  
   }