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*n*th sequence.
Note: The sequence of integers will be represented as a string.

**Understand the problem:**

The problem is kind of tricky to understand. We can use some examples to illustrate it.

For input 1112, we "count-and-say", three 1s and one 2, so it is 3112

For input 112, two 1s and one 2, 2112

For input 1234, output is 11121314.

Actually this question is not very clear. The sequence starts from string "1", then the read of first string is the next string, which is 11, then 21, then 1211, ...., note that n start from 1, so i + 1 sequence is the read of sequence i, the nth sequence is the read of sequence n - 1.

**Code (Java):**

public class Solution { public String countAndSay(int n) { if (n < 0) { return ""; } String s = "1"; for (int i = 0; i < n - 1; i++) { StringBuilder sb = new StringBuilder(); int count = 1; int j = 0; while (j < s.length()) { while (j < s.length() - 1 && s.charAt(j) == s.charAt(j + 1)) { count++; j++; } sb.append(Integer.toString(count)); sb.append(s.charAt(j)); count = 1; j++; } s = sb.toString(); } return s; } }

The above code does not work.

ReplyDeleteThe following works

public String countAndSay(int n) {

if (n < 0) {

return "";

}

String s = Integer.toString(n);

StringBuilder sb = new StringBuilder();

int i = 0;

while (i < s.length())

{

int count = 1;

while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1))

{

count++;

i++;

}

sb.append(Integer.toString(count));

sb.append(s.charAt(i));

i++;

}

return sb.toString();

}