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.
string StringPrep(string s)
{
string res;
int d = s.length();
for(int i = 0; i<d;)
{
char c = s[i];
int j = i+1;
while(j<d && s[j] == s[i])j++;
res += j-i + '0';
res += s[i];
i += j-i;
}
return res;
}
string countAndSay(int n) {
string s = "1";
for (int i = 1; i <n; i++)
{
s = StringPrep(s);
}
return s;
}
No comments:
Post a Comment