Count And Say Problem: The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
countAndSay(1) = "1"
countAndSay(n)
is the way you would “say” the digit string fromcountAndSay(n-1)
, which is then converted into a different digit string.
To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.
Example :
Input: n = 4 Output: "1211" Explanation: countAndSay(1) = "1" countAndSay(2) = say "1" = one 1 = "11" countAndSay(3) = say "11" = two 1's = "21" countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
Table of Contents
Count And Say Problem Solution
Problem Solution In Python
class Solution(object):
def countAndSay(self, n):
s0 = '1'
for i in range(1, n):
s1, k = '', 1
for j in range(1, len(s0)):
if s0[j-1] == s0[j]: k += 1
else: s1, k = s1 + str(k) + s0[j-1], 1
s1 += str(k) + s0[-1]
s0 = s1
return s0
Problem Solution In Java
public String countAndSay(int n) {
if(n == 0) return "";
String res = "1";
for(int i = 1; i <n; i++){
String s = res; res="";
int count = 1;// attention for the logic
char pre = s.charAt(0);
for(int j = 1; j < s.length(); j++){
if(s.charAt(j) == pre)
count++;
else{
res += count+""+pre;
pre = s.charAt(j);
count = 1;
}
}
res += count +""+ pre;
}
return String.valueOf(res);
}
Problem Solution In C++
class Solution {
public:
string countAndSay(int n) {
string temp="1";
string ans="";
if(n==1)return temp;
for(int i=2;i<=n;i++)
{
char value=temp[0];
int count=1;
ans="";
for(int j=1;j<temp.size();j++)
{
if(temp[j]==value)count++;
else
{
ans+=count+'0';
ans+=value;
count=1;
value=temp[j];
}
}
ans+=count+'0';
ans+=value;
temp=ans;
}
return ans;
}
};
Problem Solution In C
char* fromLast(char* last) {
char *s = last;
int count;
int index = 0;
char *result = (char*) malloc(2 * strlen(last));
while(*s != '\0') {
count = 1;
while(*s == *(s+1)) {
count++;
s++;
}
result[index++] = count + '0';
result[index++] = *(s);
s++;
}
result[index] = '\0';
return result;
}
char* countAndSay(int n) {
if(n == 1)
return "1";
return fromLast(countAndSay(n-1));
}