LeetCode 394 字符串解码 - 栈解法
思路
使用两个栈同步维护状态：
numDeque：记录每一层括号对应的重复次数。strDeque：记录每一层括号内已经解析出的字符串。
遍历到 ] 时，表示当前层结束：弹出当前层字符串和次数，重复拼接后并回上一层。
class Solution {
public String decodeString(String s) {
Deque<Integer> numDeque = new LinkedList<>();
Deque<String> strDeque = new LinkedList<>();
// 遍历到 ] 时 numDeque 和strDeque 表示 重复 num.top次 strD.top ,
numDeque.push(1);
strDeque.push("");
int i = 0;
while (i < s.length()) {
if (Character.isDigit(s.charAt(i))) {
int num = 0;
while (Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
// 数字入栈, 要保证两个循环不变量的含义, str也入栈, i++, 左括号直接跳过
i++;
numDeque.push(num);
strDeque.push("");
} else if (s.charAt(i) == ']') {
String cur = strDeque.pop();
int times = numDeque.pop();
StringBuilder sb = new StringBuilder();
for (int j = 0; j < times; j++) {
sb.append(cur);
}
// 数字出栈了, str栈顶也要维护,
strDeque.push(strDeque.pop() + sb.toString());
i++;
} else {
strDeque.push(strDeque.pop() + s.charAt(i));
i++;
}
}
return strDeque.pop();
}
}
心得
遇到左括号时入栈，是为了和右括号出栈形成配对。遍历到右括号时，说明“最近一个左括号之后”的内容已经完整，可以立刻结算并拼接回上一层。数字栈和字符串栈都遵循这个层级关系。