Count and Say
Source
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.
Have you met this question in a real interview? Yes
Example
Given n = 5, return "111221".
Note
The sequence of integers will be represented as a string.
Python
class Solution:
def countAndSay(self, n):
result="1"
for _ in range(1, n):
tmp=[]
count=1
for i in range(1, len(result)):
if result[i]==result[i-1]:
count+=1
else:
tmp.append(str(count))
tmp.append(result[i-1])
count=1
tmp.append(str(count))
tmp.append(result[-1])
result = ''.join(tmp)
return result
Java
public class Solution {
public String countAndSay(int n) {
if(n<=0){
return null;
}
StringBuilder result = new StringBuilder();
result.append("1");
for(int j=1; j<n; j++){
StringBuilder tmp = new StringBuilder();
int count=1;
for(int i=1; i<result.length(); i++){
if(result.charAt(i)==result.charAt(i-1)){
count++;
}
else{
tmp.append(count);
tmp.append(result.charAt(i-1));
count=1;
}
}
tmp.append(count);
tmp.append(result.charAt(result.length()-1));
result=tmp;
}
return result.toString();
}
}