题目
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入。s中所有整数的取值范围为[1, 300]
解题
方法一：栈
思路
维护一个栈(stack)，遍历字符串：
- 如果当前字符(
curr)是数字，解析出一个重复次数(repeat)并入栈。（具体解析见方法三说明） - 如果当前字符是字母或
'['，直接把当前字符入栈。 - 如果当前字符是
']'，说明整个字符串中某一个可解析部分已经全部入栈，且在栈顶的区域，可以开始解析： 开始出栈，把遇到'['之前的字符全部出栈并反向拼入重复部分(repeating)（与入栈的顺序相反），把'['出栈，此时的栈顶元素就是该重复部分的重复次数(repeat)，把它出栈并转为整数，新建一个容器(decoded)把repeating拼接repeat次，最后把decoded入栈，表明解析完成。
完成遍历后，把栈中的元素全部出栈，并反向拼入答案（此时栈中的元素个数其实就是原字符串中第一层需解析字符串部分(encoded_string)的个数，如 test2[ab2[e10[a]]c]3[c5[z]d]ef 遍历完成后，stack 的大小应为 2 (2[ab2[e10[a]]c] 和 3[c5[z]d])）。
代码
class Solution {
public String decodeString(String s) {
Deque<String> stack = new LinkedList<>();
for (int i = 0 ; i < s.length(); i++) {
char curr = s.charAt(i);
if (isDigit(curr)) {
// 当前字符为数字时 解析重复次数
StringBuilder repeat = new StringBuilder(String.valueOf(curr));
for (curr = s.charAt(++i); isDigit(curr); curr = s.charAt(++i)) {
repeat.append(curr);
}
// 之所以这里要自减是因为for循环体中已经定义了自增
// 而这里解析重复次数时由于要验证下一个字符还是不是数字
// 所以i不可避免的会向后移动一位, 为了避免跳过字符所以自减
i--;
stack.push(repeat.toString());
} else if (curr != ']') {
// 因为字符串中只可能有小写英文字母、数字、'['、']'
// 所以排除数字和']'就是这个条件
stack.push(String.valueOf(curr));
} else {
// 当前字符为']'时
StringBuilder repeating = new StringBuilder();
while (!"[".equals(stack.peek())) {
// 每次都加在sb的开头, 达到反向的目的
repeating.insert(0, stack.pop());
}
stack.pop(); // 把'['出栈
// 获取目前栈顶的当前部分对应的重复次数
int repeat = Integer.parseInt(stack.pop());
StringBuilder decoded = new StringBuilder();
// 拼入容器
for (; repeat > 0; repeat--) decoded.append(repeating);
stack.push(decoded.toString());
}
}
StringBuilder ans = new StringBuilder();
// 出栈并反向加入答案中
while (!stack.isEmpty()) ans.insert(0, stack.pop());
return ans.toString();
}
private boolean isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
}方法二：递归
思路
从左向右解析字符串：
- 如果当前字符为数字，那么后面一定包含一个用方括号表示的字符串，即属于这种情况：
k[...]：- 可以先解析出重复次数(
repeat)，然后解析到了'['，递归向下解析后面的内容，遇到对应的']'就返回，此时可以根据解析出的数重复次数和解析出的括号里的字符串(repeating)构造出一个新的字符串(decoded: $decoded = repeat \cdot repeating$)。 k[...]解析结束后，再次调用递归函数，解析']'右边的内容。
- 可以先解析出重复次数(
- 如果当前字符是字母，那直接解析当前这个字母，然后递归向下解析这个字母后面的内容。
代码
class Solution {
private String str;
private int pointer, len;
public String decodeString(String s) {
str = s;
pointer = 0;
len = s.length();
return decodeString();
}
private String decodeString() {
// 结束条件: 当前字符为']'或遍历完成
if (pointer == len || str.charAt(pointer) == ']') return "";
char curr = str.charAt(pointer);
if (isDigit(curr)) {
// 如果当前字符是数字 解析出一个重复次数
int repeat = curr - '0';
for (curr = str.charAt(++pointer); isDigit(curr);
curr = str.charAt(++pointer)) {
repeat = repeat * 10 + (curr - '0');
}
pointer++; // 跳过 '['
// 递归向后解析'[]'中的内容
String repeating = decodeString();
// 拼接字符串 decoded = repeat * repeating
StringBuilder decoded = new StringBuilder();
for (; repeat > 0; repeat--) decoded.append(repeating);
// 当前区域解析完成指针向后移动一位
pointer++;
// 返回当前解析结果+递归后面的解析结果
return decoded.append(decodeString()).toString();
} else if (curr != '[') {
// 如果当前字符是字母直接解析当前这个字母，然后递归向后解析这个字母后面的内容
pointer++;
return String.valueOf(curr) + decodeString();
}
return decodeString();
}
private boolean isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
}方法三：栈 递归
思路
新建一个栈，用来存放 '[' 的索引
遍历字符串：
- 如果当前字符是数字，说明遍历到了重复的次数 k：
- 如果此时栈不为空，则现在正在待解码的子字符串中，直接跳过该字符
- 记录重复次数
repeat因为重复次数最大可能是三位数，所以要看后面的字符是否是重复次数的一部分 - 所以循环下一个字符，如果不是数字就跳出，如果是数字，就加入重复次数的记录中
- 如果当前字符是
'['，说明遍历到了待解码子字符串(encoded_string)的开始标识：- 直接把 当前索引+1 进栈，作为该 encoded_string 的开始索引
- 如果当前字符是
']'，说明遍历到了待解码子字符串的结束标识：- 把对应的开始索引弹出栈
- 如果弹出后栈还不为空的话，说明这是第二层甚至更深的 encoded_string 当前遍历不需要处理，直接跳过进行下一次循环
- 这是第一层第一个遇到的 encoded_string ，截取其前面的部分(
before$ = s[0, repeatStart)$)用于拼接，截取需要处理的 encoded_string 区(repeating$ = s[start, i)$)，截取后面的部分(after$ = s[i + 1, len)$) - 因为
repeating和after中还可能有需要解码的 encoded_string ，把它们递归地做解码 - 解码完成后，把前面的部分(
before)拼入repeat次的重复部分(repeating)后再拼接上前面的部分即为解码后的字符串，直接返回
代码
class Solution {
public String decodeString(String s) {
Stack<Integer> stack = new Stack<>();
if (!s.contains("[")) return s;
int len = s.length();
int repeatStart = 0, repeat = 0;
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (isDigit(ch)) {
if (!stack.isEmpty()) continue;
repeat = ch - '0';
repeatStart = i;
for (char next = s.charAt(i + 1); isDigit(next); i++, next = s.charAt(i + 1)) {
repeat = repeat * 10 + (next - '0');
}
} else if (ch == '[') {
stack.push(i + 1);
} else if (ch == ']') {
int start = stack.pop();
if (!stack.isEmpty()) continue;
StringBuilder before = new StringBuilder(s.substring(0, repeatStart));
String repeating = decodeString(s.substring(start, i));
String after = decodeString(s.substring(i + 1, len));
for (; repeat > 0; repeat--) before.append(repeating);
return before.append(after).toString();
}
}
return s;
}
private boolean isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
}
评论区