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.
Example:
if n = 2,
the sequence is 11.
Method:
Construct the sequence one by one by definition..
Solution:
Time: O(2^n) -> the average rate of growth between sequences is (0, 2)
Space: O(2^n)
public class Solution {
public String countAndSay(int A) {
String say = "1";
for (int i = 1; i < A; i ++) {
char[] arr = say.toCharArray();
StringBuilder nextSay = new StringBuilder();
Character prev = null;
int count = 0;
for (int j = 0; j < arr.length; j ++) {
Character c = arr[j];
if (c == prev) {
count ++;
} else if (prev != null) {
nextSay.append("" + count);
nextSay.append("" + prev);
count = 1;
} else {
count = 1;
}
prev = c;
}
if (prev != null) {
nextSay.append("" + count);
nextSay.append("" + prev);
}
say = nextSay.toString();
}
return say;
}
}