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.
1function countAndSay(n) {
2 let result = "1";
3
4 for (let i = 1; i < n; i++) {
5 let current = "";
6 for (let j = 0; j < result.length; ) {
7 let count = 0;
8 const currentChar = result[j];
9 while (j < result.length && result[j] === currentChar) {
10 j++;
11 count++;
12 }
13 current += `${count}${currentChar}`;
14 }
15 result = current;
16 }
17
18 return result;
19}
20
21console.log(countAndSay(4));In JavaScript, string concatenation is used within a loop to form the increasingly complex sequences by counting and describing each sequence of repeated digits.
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.
1using System.Text;
public class Solution {
private string NextSequence(string seq) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < seq.Length;) {
char currentChar = seq[i];
int count = 0;
while (i < seq.Length && seq[i] == currentChar) {
i++;
count++;
}
result.Append(count).Append(currentChar);
}
return result.ToString();
}
public string CountAndSay(int n) {
if (n == 1) return "1";
string prevResult = CountAndSay(n - 1);
return NextSequence(prevResult);
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.CountAndSay(4));
}
}C# implementation makes use of recursion to compute sequences with NextSequence extending every string based on counting each digit from previous results.