Problem: 394. 字符串解码

思路

👨‍🏫 路飞

💖 辅助栈

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {public String decodeString(String s){StringBuilder res = new StringBuilder();int k = 0;// 记录当前的重复 次数Stack<Integer> stackMul = new Stack<>();// 重复次数 栈Stack<String> stackRes = new Stack<>();// 每个 k[str]内的 str 栈for (char c : s.toCharArray()){if (c == '['){
//				碰到左括号，记录 K 和 当前res,归零stackMul.add(k);stackRes.add(res.toString());k = 0;res = new StringBuilder();} else if (c == ']'){
//				处理前边最近的一个 k[str] StringBuilder str = new StringBuilder();int kk = stackMul.pop();for (int i = 0; i < kk; i++)str.append(res);
//				之前的字符串 栈顶元素，再拼接上 当前的 strres = new StringBuilder(stackRes.pop() + str);} else if (c >= '0' && c <= '9')// 数字，还得考虑 k 是多位数的情况k = k * 10 + Integer.parseInt(c + "");else// 是普通字符res.append(c);}return res.toString();}
}