# Count and Say

## Question

### Problem Statement

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.

## 题解1 - 迭代

### Python

class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n <= 0:
return ''
seq = '1'
for _ in range(n - 1):
seq = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), seq)

return seq


### Python

class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n <= 0:
return ''

curr_seq = '1'
for j in range(n - 1):
curr_seq = self._get_next_seq(curr_seq)

return curr_seq

def _get_next_seq(self, seq):
next_seq = ''
cnt = 1
for i in range(len(seq)):
if i + 1 < len(seq) and seq[i] == seq[i + 1]:
cnt += 1
else:
next_seq += str(cnt)
next_seq += seq[i]
cnt = 1

return next_seq


### C++

class Solution {
public:
string countAndSay(int n) {
if (n <= 0) return "";

string curr_seq = "1";
while (--n) {
curr_seq = getNextSeq(curr_seq);
}

return curr_seq;
}

private:
string getNextSeq(string seq) {
string next_seq = "";
int cnt = 1;
for (int i = 0; i < seq.length(); i++) {
if (i + 1 < seq.length() && seq[i] == seq[i + 1]) {
cnt++;
} else {
next_seq.push_back('0' + cnt);
next_seq.push_back(seq[i]);
cnt = 1;
}
}

return next_seq;
}
};


### Java

public class Solution {
public String countAndSay(int n) {
assert n > 0;
StringBuilder currSeq = new StringBuilder("1");
for (int i = 1; i < n; i++) {
currSeq = getNextSeq(currSeq);
}
return currSeq.toString();
}

private StringBuilder getNextSeq(StringBuilder seq) {
StringBuilder nextSeq = new StringBuilder();
int cnt = 1;
for (int i = 0; i < seq.length(); i++) {
if (i + 1 < seq.length() && seq.charAt(i) == seq.charAt(i + 1)) {
cnt++;
} else {
nextSeq.append(cnt).append(seq.charAt(i));
cnt = 1;
}
}
return nextSeq;
}
}


## 题解2 - 递归

### Python

class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n <= 0:
return ''
if n == 1:
return '1'
seq = self.countAndSay(n - 1)
next_seq = ''
cnt = 1
for i in range(len(seq)):
if i + 1 < len(seq) and seq[i] == seq[i + 1]:
cnt += 1
else:
next_seq += str(cnt)
next_seq += seq[i]
cnt = 1

return next_seq


### C++

class Solution {
public:
string countAndSay(int n) {
if (n <= 0) return "";
if (n == 1) return "1";

string seq = countAndSay(n - 1);
string next_seq = "";
int cnt = 1;
for (int i = 0; i < seq.length(); i++) {
if (i + 1 < seq.length() && seq[i] == seq[i + 1]) {
cnt++;
} else {
next_seq.push_back('0' + cnt);
next_seq.push_back(seq[i]);
cnt = 1;
}
}

return next_seq;
}
};


### Java

public class Solution {
public String countAndSay(int n) {
assert n > 0;
if (n == 1) return "1";

String seq = countAndSay(n - 1);
StringBuilder nextSeq = new StringBuilder();
int cnt = 1;
for (int i = 0; i < seq.length(); i++) {
if (i + 1 < seq.length() && seq.charAt(i) == seq.charAt(i + 1)) {
cnt++;
} else {
nextSeq.append(cnt).append(seq.charAt(i));
cnt = 1;
}
}

return nextSeq.toString();
}
}