Sponsored
This approach involves constructing the sequence iteratively. We start from the base case, which is '1', and iteratively build up the strings by counting and saying the digits from the last constructed string.
Time Complexity: O(2^n) as the length of the string grows exponentially.
Space Complexity: O(2^n) for storing the string.
1public class Solution {
2 public String countAndSay(int n) {
3 String result = "1";
4 for (int i = 1; i < n; i++) {
5 StringBuilder temp = new StringBuilder();
6 for (int j = 0; j < result.length(); ) {
7 char current_digit = result.charAt(j);
8 int count = 0;
9 while (j < result.length() && result.charAt(j) == current_digit) {
10 count++;
11 j++;
12 }
13 temp.append(count).append(current_digit);
14 }
15 result = temp.toString();
16 }
17 return result;
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 System.out.println(sol.countAndSay(4));
23 }
24}The Java implementation uses a StringBuilder to efficiently construct the next sequence by counting the occurrences of each digit consecutively.
The recursive approach defines the function countAndSay recursively by computing countAndSay(n-1), then generating the count-and-say encoding for it.
This method involves less memory usage on the function stack compared to an iterative approach but still leverages recursion for elegance.
Time Complexity: O(2^n) as strings grow exponentially.
Space Complexity: O(2^n) due to storing strings and O(n) recursion stack.
1#include <string>
using namespace std;
string nextSequence(const string& seq) {
string result = "";
for (int i = 0; i < seq.length(); ) {
char current_digit = seq[i];
int count = 0;
while (i < seq.length() && seq[i] == current_digit) {
count++;
i++;
}
result += to_string(count) + current_digit;
}
return result;
}
string countAndSay(int n) {
if (n == 1) return "1";
string prev_result = countAndSay(n - 1);
return nextSequence(prev_result);
}
int main() {
cout << countAndSay(4) << endl;
return 0;
}C++ uses a helper function nextSequence for generating sequences. Recursion handles calculate series where each call depends on calculating the previous pattern.