38: Count-and-Say
Medium
This question is just an implementation question; its quite linear, meaning you really just need to follow step-by-step the algorithm that they have described.
In my case, I just defined a recursive function that breaks when we have ran the pre-determined number of recursions. In it, I just simply iterate till I reach a number that is different, then append the number of times that I have seen that number in a row, alongside the value of the number that I was iterating for. I repeat this until I reach the end of the string, and then return the resultant string if enough recursions have occurred.
Code:
class Solution {
public:
string RLE (string curr_sequence, int counter) {
if (counter == 1){
return curr_sequence;
}
string next_sequence = "";
int left = 0, right;
for (; left < curr_sequence.size();) {
for (right = left; right < curr_sequence.size() && curr_sequence[left] == curr_sequence[right]; ++right);
next_sequence += to_string(right-left);
next_sequence += curr_sequence[left];
left = right;
}
return RLE(next_sequence, counter-1);
}
string countAndSay(int n) {
return RLE("1", n);
}
};