394. 字符串解码
题目描述
输入一个编码后的字符串 s，返回解码结果。
编码规则：k[encoded_string] 表示方括号里的内容要重复 k 次，k 是正整数。方括号可以嵌套，应先解开内层再展开外层。不在任何方括号里的字母原样保留。
输入一定合法：没有多余的空格，方括号总能正确配对。原文中不含数字，数字只用作重复次数，所以不会出现 3a、2[4] 这样的写法。
题目保证解码结果的长度不超过 10^5。
示例 1
输入：s = "3[a]2[bc]" 输出："aaabcbc"
解释：a 重复 3 次，bc 重复 2 次，再拼起来。
示例 2
输入：s = "3[a2[c]]" 输出："accaccacc"
解释：内层 a2[c] 先展开成 acc，再整体重复 3 次。
示例 3
输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef"
解释：abc 重复 2 次，cd 重复 3 次，最后接上 ef。
数据范围
1 <= s.length <= 30s由小写英文字母、数字和方括号[]组成s一定是合法编码s中所有整数都在[1, 300]范围内
解题思路：栈
栈保存嵌套层的字符串和倍数。
为什么正确
栈保存每个嵌套层进入时的上下文。
复杂度分析
时间 O(n)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def decodeString(self,s):
st=[];cur='';num=0
for c in s:
if c.isdigit():num=num*10+int(c)
elif c=='[':st.append((cur,num));cur='';num=0
elif c==']':prev,k=st.pop();cur=prev+cur*k
else:cur+=c
return curclass Solution {
record Frame(String cur, int num) {}
public String decodeString(String s) {
Deque<Frame> st = new ArrayDeque<>(); String cur = ""; int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) num = num * 10 + (c - '0');
else if (c == '[') { st.push(new Frame(cur, num)); cur = ""; num = 0; }
else if (c == ']') { Frame f = st.pop(); cur = f.cur() + cur.repeat(f.num()); }
else cur += c;
}
return cur;
}
}class Solution {
public:
string decodeString(string s) {
vector<pair<string, int>> st; string cur; int num = 0;
for (char c : s) {
if (isdigit(c)) num = num * 10 + (c - '0');
else if (c == '[') { st.push_back({cur, num}); cur = ""; num = 0; }
else if (c == ']') {
auto [prev, k] = st.back(); st.pop_back();
string t = prev;
while (k--) t += cur;
cur = t;
}
else cur += c;
}
return cur;
}
};func decodeString(s string) string {
type frame struct {
cur string
num int
}
st, cur, num := []frame{}, "", 0
for i := 0; i < len(s); i++ {
c := s[i]
if c >= '0' && c <= '9' {
num = num*10 + int(c-'0')
} else if c == '[' {
st = append(st, frame{cur, num}); cur = ""; num = 0
} else if c == ']' {
f := st[len(st)-1]; st = st[:len(st)-1]
cur = f.cur + strings.Repeat(cur, f.num)
} else {
cur += string(c)
}
}
return cur
}var decodeString = function(s) {
const st = []; let cur = '', num = 0;
for (const c of s) {
if (c >= '0' && c <= '9') num = num * 10 + Number(c);
else if (c === '[') { st.push([cur, num]); cur = ''; num = 0; }
else if (c === ']') { const [prev, k] = st.pop(); cur = prev + cur.repeat(k); }
else cur += c;
}
return cur;
};function decodeString(s: string): string {
const st: [string, number][] = []; let cur = '', num = 0;
for (const c of s) {
if (c >= '0' && c <= '9') num = num * 10 + Number(c);
else if (c === '[') { st.push([cur, num]); cur = ''; num = 0; }
else if (c === ']') { const [prev, k] = st.pop()!; cur = prev + cur.repeat(k); }
else cur += c;
}
return cur;
};其他解法
两种方法都是线性扫描；栈手动保存每层的上下文，递归下降让调用栈自动保存上下文。
解法 2：递归下降 时间 O(n)，空间 O(n)
用一个全局下标从左到右读字符串。函数 parse 不断读取字母，遇到数字就读出倍数 k，跳过 '[' 后递归调用 parse 得到括号内的串，再跳过 ']'，把它重复 k 次接到结果后面。遇到 ']' 或读完时返回当前结果。
递归调用栈代替了显式栈，结构和文法一一对应，更容易扩展到更复杂的表达式。嵌套很深时要注意递归深度。
class Solution:
def decodeString(self, s):
self.i = 0
def parse():
res = []
while self.i < len(s) and s[self.i] != ']':
c = s[self.i]
if c.isdigit():
k = 0
while s[self.i].isdigit():
k = k * 10 + int(s[self.i])
self.i += 1
self.i += 1
sub = parse()
self.i += 1
res.append(sub * k)
else:
res.append(c)
self.i += 1
return ''.join(res)
return parse()class Solution {
int i = 0;
String parse(String s) {
StringBuilder res = new StringBuilder();
while (i < s.length() && s.charAt(i) != ']') {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int k = 0;
while (Character.isDigit(s.charAt(i))) k = k * 10 + (s.charAt(i++) - '0');
i++;
String sub = parse(s);
i++;
res.append(sub.repeat(k));
} else {
res.append(c);
i++;
}
}
return res.toString();
}
public String decodeString(String s) {
i = 0;
return parse(s);
}
}class Solution {
public:
int i = 0;
string parse(const string& s) {
string res;
while (i < (int)s.size() && s[i] != ']') {
char c = s[i];
if (isdigit(c)) {
int k = 0;
while (isdigit(s[i])) k = k * 10 + (s[i++] - '0');
i++;
string sub = parse(s);
i++;
while (k--) res += sub;
} else {
res += c;
i++;
}
}
return res;
}
string decodeString(string s) {
i = 0;
return parse(s);
}
};func decodeString(s string) string {
i := 0
var parse func() string
parse = func() string {
res := []byte{}
for i < len(s) && s[i] != ']' {
c := s[i]
if c >= '0' && c <= '9' {
k := 0
for s[i] >= '0' && s[i] <= '9' {
k = k*10 + int(s[i]-'0')
i++
}
i++
sub := parse()
i++
for ; k > 0; k-- {
res = append(res, sub...)
}
} else {
res = append(res, c)
i++
}
}
return string(res)
}
return parse()
}var decodeString = function(s) {
let i = 0;
const isDigit = c => c >= '0' && c <= '9';
const parse = () => {
let res = '';
while (i < s.length && s[i] !== ']') {
const c = s[i];
if (isDigit(c)) {
let k = 0;
while (isDigit(s[i])) k = k * 10 + Number(s[i++]);
i++;
const sub = parse();
i++;
res += sub.repeat(k);
} else {
res += c;
i++;
}
}
return res;
};
return parse();
};function decodeString(s: string): string {
let i = 0;
const isDigit = (c: string) => c >= '0' && c <= '9';
const parse = (): string => {
let res = '';
while (i < s.length && s[i] !== ']') {
const c = s[i];
if (isDigit(c)) {
let k = 0;
while (isDigit(s[i])) k = k * 10 + Number(s[i++]);
i++;
const sub = parse();
i++;
res += sub.repeat(k);
} else {
res += c;
i++;
}
}
return res;
};
return parse();
}