Count and Say (Java)

Leetcode

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.

	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();
	}
	}

view raw CountAndSay.java hosted with ❤ by GitHub