LeetCode 394: Decode String (Stack-Based Nested Expansion)
LeetCode 394StackStringInterviewToday we solve LeetCode 394 - Decode String.
Source: https://leetcode.com/problems/decode-string/
English
Problem Summary
Given an encoded string where patterns follow k[encoded_string], return its decoded result. Nested brackets are allowed, and k can be multiple digits.
Key Insight
Use a stack to freeze current context when entering a bracket: previous built string + repeat count. When ] is reached, pop context and expand once.
Brute Force and Limitations
Recursive parsing works, but stack parsing is iterative, explicit, and easier to control in interviews (especially for multi-digit counts and deeply nested patterns).
Optimal Algorithm Steps
1) Traverse characters left to right.
2) If digit: build num = num * 10 + digit.
3) If [: push current string and num, then reset both.
4) If letter: append to current builder.
5) If ]: pop repeat count and previous string, then current = previous + current * repeat.
Complexity Analysis
Time: O(n + |answer|).
Space: O(n) for stack + builders.
Common Pitfalls
- Forgetting multi-digit repeat counts (e.g. 12[a]).
- Not resetting num after pushing at [.
- Mixing up pop order (count and previous string).
- Repeated string concatenation in loops causing overhead.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> strStack = new ArrayDeque<>();
StringBuilder curr = new StringBuilder();
int num = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr = new StringBuilder();
} else if (ch == ']') {
int repeat = countStack.pop();
StringBuilder prev = strStack.pop();
for (int i = 0; i < repeat; i++) prev.append(curr);
curr = prev;
} else {
curr.append(ch);
}
}
return curr.toString();
}
}func decodeString(s string) string {
countStack := []int{}
strStack := []string{}
curr := ""
num := 0
for _, ch := range s {
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else if ch == '[' {
countStack = append(countStack, num)
strStack = append(strStack, curr)
num = 0
curr = ""
} else if ch == ']' {
repeat := countStack[len(countStack)-1]
countStack = countStack[:len(countStack)-1]
prev := strStack[len(strStack)-1]
strStack = strStack[:len(strStack)-1]
expanded := ""
for i := 0; i < repeat; i++ {
expanded += curr
}
curr = prev + expanded
} else {
curr += string(ch)
}
}
return curr
}class Solution {
public:
string decodeString(string s) {
stack<int> countStack;
stack<string> strStack;
string curr;
int num = 0;
for (char ch : s) {
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr.clear();
} else if (ch == ']') {
int repeat = countStack.top();
countStack.pop();
string prev = strStack.top();
strStack.pop();
string expanded;
expanded.reserve(curr.size() * repeat);
for (int i = 0; i < repeat; ++i) expanded += curr;
curr = prev + expanded;
} else {
curr.push_back(ch);
}
}
return curr;
}
};class Solution:
def decodeString(self, s: str) -> str:
count_stack = []
str_stack = []
curr = []
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
count_stack.append(num)
str_stack.append(''.join(curr))
num = 0
curr = []
elif ch == ']':
repeat = count_stack.pop()
prev = str_stack.pop()
curr = [prev + ''.join(curr) * repeat]
else:
curr.append(ch)
return ''.join(curr)var decodeString = function(s) {
const countStack = [];
const strStack = [];
let curr = '';
let num = 0;
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
num = num * 10 + Number(ch);
} else if (ch === '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr = '';
} else if (ch === ']') {
const repeat = countStack.pop();
const prev = strStack.pop();
curr = prev + curr.repeat(repeat);
} else {
curr += ch;
}
}
return curr;
};中文
题目概述
给定编码字符串，格式为 k[encoded_string]，返回解码后的结果。支持多层嵌套，且 k 可能是多位数字。
核心思路
遇到 [ 时把当前上下文（已构建字符串 + 重复次数）压栈冻结；遇到 ] 时出栈并完成一次展开拼接。
暴力解法与不足
递归下降解析也能做，但迭代栈法结构更清晰、状态可控，在面试中更易解释多位数字和深层嵌套处理。
最优算法步骤
1）从左到右扫描字符。
2）若是数字：累计 num = num * 10 + digit。
3）若是 [：压入当前字符串与 num，并重置。
4）若是字母：追加到当前构建器。
5）若是 ]：弹出重复次数和上一层字符串，执行 current = previous + current * repeat。
复杂度分析
时间复杂度：O(n + |答案长度|)。
空间复杂度：O(n)。
常见陷阱
- 忽略多位数字（如 12[a]）。
- 在 [ 后忘记把 num 置零。
- 出栈顺序写反（重复次数/前缀字符串）。
- 在循环里频繁低效拼接大字符串。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String decodeString(String s) {
Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> strStack = new ArrayDeque<>();
StringBuilder curr = new StringBuilder();
int num = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr = new StringBuilder();
} else if (ch == ']') {
int repeat = countStack.pop();
StringBuilder prev = strStack.pop();
for (int i = 0; i < repeat; i++) prev.append(curr);
curr = prev;
} else {
curr.append(ch);
}
}
return curr.toString();
}
}func decodeString(s string) string {
countStack := []int{}
strStack := []string{}
curr := ""
num := 0
for _, ch := range s {
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else if ch == '[' {
countStack = append(countStack, num)
strStack = append(strStack, curr)
num = 0
curr = ""
} else if ch == ']' {
repeat := countStack[len(countStack)-1]
countStack = countStack[:len(countStack)-1]
prev := strStack[len(strStack)-1]
strStack = strStack[:len(strStack)-1]
expanded := ""
for i := 0; i < repeat; i++ {
expanded += curr
}
curr = prev + expanded
} else {
curr += string(ch)
}
}
return curr
}class Solution {
public:
string decodeString(string s) {
stack<int> countStack;
stack<string> strStack;
string curr;
int num = 0;
for (char ch : s) {
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr.clear();
} else if (ch == ']') {
int repeat = countStack.top();
countStack.pop();
string prev = strStack.top();
strStack.pop();
string expanded;
expanded.reserve(curr.size() * repeat);
for (int i = 0; i < repeat; ++i) expanded += curr;
curr = prev + expanded;
} else {
curr.push_back(ch);
}
}
return curr;
}
};class Solution:
def decodeString(self, s: str) -> str:
count_stack = []
str_stack = []
curr = []
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
count_stack.append(num)
str_stack.append(''.join(curr))
num = 0
curr = []
elif ch == ']':
repeat = count_stack.pop()
prev = str_stack.pop()
curr = [prev + ''.join(curr) * repeat]
else:
curr.append(ch)
return ''.join(curr)var decodeString = function(s) {
const countStack = [];
const strStack = [];
let curr = '';
let num = 0;
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
num = num * 10 + Number(ch);
} else if (ch === '[') {
countStack.push(num);
strStack.push(curr);
num = 0;
curr = '';
} else if (ch === ']') {
const repeat = countStack.pop();
const prev = strStack.pop();
curr = prev + curr.repeat(repeat);
} else {
curr += ch;
}
}
return curr;
};
Comments