Description:
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
countAndSay(1) = "1"countAndSay(n)is the run-length encoding ofcountAndSay(n - 1).
Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".
Given a positive integer n, return the nth element of the count-and-say sequence.
Examples:
Example 1:
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"
Example 2:
Input: n = 1
Output: "1"
Explanation:
This is the base case.Solution in Python:
Python
class Solution:
def countAndSay(self, n: int) -> str:
# Base case: the first element of the sequence is always "1"
if n == 1:
return "1"
# Recursive call: get the previous element in the sequence
prev_sequence = self.countAndSay(n - 1)
# Initialize an empty result string
result = ""
# Initialize variables to keep track of the current character and its count
current_char = prev_sequence[0]
count = 1
# Iterate over the previous sequence starting from the second character
for char in prev_sequence[1:]:
if char == current_char:
# If the current character is the same as the previous one, increment the count
count += 1
else:
# If the current character is different, append the count and the character to the result
result += str(count) + current_char
# Reset the current character and its count
current_char = char
count = 1
# Append the count and character for the last group
result += str(count) + current_char
return resultExplanation:
- Base Case:
- If
nis 1, return the string “1”. This is the starting point of the sequence.
- If
- Recursive Call:
- For any
ngreater than 1, we first get the sequence forn-1by making a recursive call tocountAndSay(n - 1).
- For any
- Initialize Variables:
result: An empty string to build the next sequence.current_char: The first character of the previous sequence.count: Counter for the occurrences ofcurrent_char.
- Iterate Over the Previous Sequence:
- Start from the second character and iterate through each character in the previous sequence.
- If the current character is the same as
current_char, increment the count. - If the current character is different, append the count and
current_chartoresult, then resetcurrent_charto the current character and reset the count to 1.
- Final Append:
- After the loop, append the count and
current_charfor the last group toresult.
- After the loop, append the count and
- Return Result:
- Return the built
resultstring which is the sequence for the givenn.
- Return the built
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
// Base case: the first element of the sequence is always "1"
if (n === 1) {
return "1";
}
// Recursive call: get the previous element in the sequence
let prevSequence = countAndSay(n - 1);
// Initialize an empty result string
let result = "";
// Initialize variables to keep track of the current character and its count
let currentChar = prevSequence[0];
let count = 1;
// Iterate over the previous sequence starting from the second character
for (let i = 1; i < prevSequence.length; i++) {
if (prevSequence[i] === currentChar) {
// If the current character is the same as the previous one, increment the count
count += 1;
} else {
// If the current character is different, append the count and the character to the result
result += count.toString() + currentChar;
// Reset the current character and its count
currentChar = prevSequence[i];
count = 1;
}
}
// Append the count and character for the last group
result += count.toString() + currentChar;
return result;
};Solution in Java:
Java
class Solution {
public String countAndSay(int n) {
// Base case: the first element of the sequence is always "1"
if (n == 1) {
return "1";
}
// Recursive call: get the previous element in the sequence
String prevSequence = countAndSay(n - 1);
// Initialize a StringBuilder to build the next sequence
StringBuilder result = new StringBuilder();
// Initialize variables to keep track of the current character and its count
char currentChar = prevSequence.charAt(0);
int count = 1;
// Iterate over the previous sequence starting from the second character
for (int i = 1; i < prevSequence.length(); i++) {
if (prevSequence.charAt(i) == currentChar) {
// If the current character is the same as the previous one, increment the count
count += 1;
} else {
// If the current character is different, append the count and the character to the result
result.append(count).append(currentChar);
// Reset the current character and its count
currentChar = prevSequence.charAt(i);
count = 1;
}
}
// Append the count and character for the last group
result.append(count).append(currentChar);
return result.toString();
}
}Solution in C#:
C#
public class Solution {
public string CountAndSay(int n) {
// Base case: the first element of the sequence is always "1"
if (n == 1) {
return "1";
}
// Recursive call: get the previous element in the sequence
string prevSequence = CountAndSay(n - 1);
// Initialize a StringBuilder to build the next sequence
StringBuilder result = new StringBuilder();
// Initialize variables to keep track of the current character and its count
char currentChar = prevSequence[0];
int count = 1;
// Iterate over the previous sequence starting from the second character
for (int i = 1; i < prevSequence.Length; i++) {
if (prevSequence[i] == currentChar) {
// If the current character is the same as the previous one, increment the count
count += 1;
} else {
// If the current character is different, append the count and the character to the result
result.Append(count).Append(currentChar);
// Reset the current character and its count
currentChar = prevSequence[i];
count = 1;
}
}
// Append the count and character for the last group
result.Append(count).Append(currentChar);
return result.ToString();
}
}