Countand Say Algorithm
The Count and Say algorithm is a sequence-based algorithm that generates a series of numbers in which each term is derived by counting the occurrences of consecutive elements in the previous term. It is a widely used algorithm in computer science and mathematics, with applications ranging from pattern recognition to data compression. The algorithm typically starts with the number 1, then proceeds by counting the frequency of each digit in the previous term and appending that count followed by the digit itself, thus forming the next term in the sequence.
For example, the first term in the sequence is 1. The second term is generated by counting the occurrences of the digit 1 in the first term, which is one occurrence, and appending the digit 1 to the count, resulting in the term "11". The third term is generated by counting the occurrences of the digits in the second term, which has two 1s, yielding the term "21". The process continues in this manner, generating subsequent terms such as "1211", "111221", and so on. The Count and Say algorithm is particularly useful in problems involving the analysis of sequences and the identification of patterns or repetitions within a given dataset.
class Solution {
public:
string countAndSay(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string begin = "1";
for (int i = 0; i < n - 1; i++) {
string next;
int start = 0;
while (start < begin.size()) {
int end = start;
int count = 0;
while (end < begin.size() && begin[start] == begin[end]) {
end += 1;
count += 1;
}
next += char('0' + count);
next += begin[start];
start = end;
}
begin = next;
}
return begin;
}
};
