LeetCode 38: Count and Say (Run-Length Encoding Simulation)
LeetCode 38StringSimulationRun-Length EncodingToday we solve LeetCode 38 - Count and Say.
Source: https://leetcode.com/problems/count-and-say/
English
Problem Summary
The sequence starts from "1". Each next term is produced by reading the previous term in groups of consecutive equal digits: say the count first, then the digit. Return the n-th term.
Key Insight
This is iterative run-length encoding (RLE). For each round, scan the current string once, compress consecutive groups into count + digit, and use that as the next string.
Brute Force and Limitations
Trying recursion that repeatedly slices strings works but often creates extra temporary objects and is harder to reason about. A clean iterative pass per round is simpler and efficient enough.
Optimal Algorithm Steps
1) Start with cur = "1".
2) Repeat from round 2 to round n.
3) Scan cur with pointer i, extend j while cur[j] == cur[i].
4) Append (j - i) and cur[i] to builder.
5) Set cur = builder for next round.
Complexity Analysis
Let L be the length of the final string. Each round scans its current string once, so total time is proportional to generated output size: O(total generated chars) (commonly described as O(L) per final round perspective).
Space: O(L).
Common Pitfalls
- Forgetting to append the last group after loop.
- Mixing char and integer append order (must be count then digit).
- Off-by-one in the inner pointer movement.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String countAndSay(int n) {
String cur = "1";
for (int round = 2; round <= n; round++) {
StringBuilder next = new StringBuilder();
int i = 0;
while (i < cur.length()) {
int j = i;
while (j < cur.length() && cur.charAt(j) == cur.charAt(i)) {
j++;
}
next.append(j - i).append(cur.charAt(i));
i = j;
}
cur = next.toString();
}
return cur;
}
}import "strconv"
func countAndSay(n int) string {
cur := "1"
for round := 2; round <= n; round++ {
next := make([]byte, 0)
for i := 0; i < len(cur); {
j := i
for j < len(cur) && cur[j] == cur[i] {
j++
}
next = append(next, []byte(strconv.Itoa(j-i))...)
next = append(next, cur[i])
i = j
}
cur = string(next)
}
return cur
}class Solution {
public:
string countAndSay(int n) {
string cur = "1";
for (int round = 2; round <= n; ++round) {
string next;
for (int i = 0; i < (int)cur.size();) {
int j = i;
while (j < (int)cur.size() && cur[j] == cur[i]) {
++j;
}
next += to_string(j - i);
next.push_back(cur[i]);
i = j;
}
cur = move(next);
}
return cur;
}
};class Solution:
def countAndSay(self, n: int) -> str:
cur = "1"
for _ in range(2, n + 1):
parts = []
i = 0
while i < len(cur):
j = i
while j < len(cur) and cur[j] == cur[i]:
j += 1
parts.append(str(j - i))
parts.append(cur[i])
i = j
cur = "".join(parts)
return curvar countAndSay = function(n) {
let cur = "1";
for (let round = 2; round <= n; round++) {
const parts = [];
for (let i = 0; i < cur.length;) {
let j = i;
while (j < cur.length && cur[j] === cur[i]) {
j++;
}
parts.push(String(j - i));
parts.push(cur[i]);
i = j;
}
cur = parts.join("");
}
return cur;
};中文
题目概述
序列从 "1" 开始。每一轮都“读出”上一轮字符串中连续相同数字的分组：先报数量，再报数字本身。返回第 n 项。
核心思路
本质是对字符串做迭代版游程编码（RLE）。每轮线性扫描当前串，把每个连续段压缩成 数量 + 数字，得到下一轮。
暴力解法与不足
递归 + 频繁切片也能做，但临时对象更多、实现更绕。迭代双指针分组更直观，稳定通过所有约束。
最优算法步骤
1）初始化 cur = "1"。
2）从第 2 轮迭代到第 n 轮。
3）用 i 定位当前组起点，j 向右扩展到不同字符。
4）把 (j - i) 和 cur[i] 依次写入结果。
5）本轮结束后更新 cur。
复杂度分析
设最终字符串长度为 L。每轮对当前串只扫描一次，总体与生成字符总量同阶；常见描述可视作最终规模下的线性处理。
空间复杂度：O(L)。
常见陷阱
- 循环结束漏写最后一组。
- 把“数字+数量”写反（正确是“数量+数字”）。
- 内层指针边界处理错误导致越界或死循环。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String countAndSay(int n) {
String cur = "1";
for (int round = 2; round <= n; round++) {
StringBuilder next = new StringBuilder();
int i = 0;
while (i < cur.length()) {
int j = i;
while (j < cur.length() && cur.charAt(j) == cur.charAt(i)) {
j++;
}
next.append(j - i).append(cur.charAt(i));
i = j;
}
cur = next.toString();
}
return cur;
}
}import "strconv"
func countAndSay(n int) string {
cur := "1"
for round := 2; round <= n; round++ {
next := make([]byte, 0)
for i := 0; i < len(cur); {
j := i
for j < len(cur) && cur[j] == cur[i] {
j++
}
next = append(next, []byte(strconv.Itoa(j-i))...)
next = append(next, cur[i])
i = j
}
cur = string(next)
}
return cur
}class Solution {
public:
string countAndSay(int n) {
string cur = "1";
for (int round = 2; round <= n; ++round) {
string next;
for (int i = 0; i < (int)cur.size();) {
int j = i;
while (j < (int)cur.size() && cur[j] == cur[i]) {
++j;
}
next += to_string(j - i);
next.push_back(cur[i]);
i = j;
}
cur = move(next);
}
return cur;
}
};class Solution:
def countAndSay(self, n: int) -> str:
cur = "1"
for _ in range(2, n + 1):
parts = []
i = 0
while i < len(cur):
j = i
while j < len(cur) and cur[j] == cur[i]:
j += 1
parts.append(str(j - i))
parts.append(cur[i])
i = j
cur = "".join(parts)
return curvar countAndSay = function(n) {
let cur = "1";
for (let round = 2; round <= n; round++) {
const parts = [];
for (let i = 0; i < cur.length;) {
let j = i;
while (j < cur.length && cur[j] === cur[i]) {
j++;
}
parts.push(String(j - i));
parts.push(cur[i]);
i = j;
}
cur = parts.join("");
}
return cur;
};
Comments