Count and Say

CountAndSay.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.

// 2/8/2014 rewrite, interative version

public class CountAndSay {
    public String countAndSay(int n) {
        if (n<1){
            return null;
        }
        int i=2;
        String current="1";
        while (i<=n){
            current=say(current);
            i++;
        }
        
        return current;
    }
    
    // count each char in given input string
    private String say(String input){
        char last=input.charAt(0);
        
        String result="";
        
        int i=1;// index
        
        int count=1;// count for each char
        while (i<input.length()){
            if (input.charAt(i)==last){
                count++;
            }
            else{
                result+=count;
                result+=last;
                
                last=input.charAt(i);
                count=1;
                
            }
            
            i++;
            
        }
        
        result+=count;
        result+=last;
        
        return result;
        
    }
}

// below is recursive version 
Time Complexity  O(n^2)

public class Solution {
    public String countAndSay(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (n<=1){
            return String.valueOf(1);
        }
        else{
            
            return say(countAndSay(n-1));
        }
        
       
    }
    private String say(String s){
        
        int i=0;
        int count=1;
        StringBuffer sb=new StringBuffer();
        
        while(i<s.length()){
            int j=i+1;
            
            while(j<s.length()&&s.charAt(j)==s.charAt(i)){
                count++;
                j++;
            }
            
            sb.append(count);
            sb.append(s.charAt(i));
            
            i=j;
            count=1;
        }
        return sb.toString();
        
    }
}