LeetCode [394] 字符串解码
题目
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: 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"
解答：
package com.lyw.leetcode.editor.cn;
import java.util.Stack;
public class DecodeString{
public static void main(String[] args) {
Solution solution = new DecodeString().new Solution();
String s = solution.decodeString("abc3[cd]xyz");
System.out.println(s);
}
class Solution {
public String decodeString(String s) {
// 入栈
MyQueue stack = new MyQueue();
// 中括号解析栈
Stack<Character> stackB = new Stack<>();
for (int i = 0; i < s.length(); i++) {
stack.push(s.charAt(i));
}
StringBuilder stringBuilder = new StringBuilder();
// 依次取字母,判别
// 1. 字母 放入字符串
// 2. 数字 解析数字大小，将中括号内的字符递归传入函数解析，返回后乘以数字
String result = null;
int len = 0;
while (!stack.empty()) {
//将字母添加到字符串
if (!Character.isDigit(stack.peek())) {
stringBuilder.append(stack.pop());
} else {
// 解析数字大小
StringBuilder temp = new StringBuilder();
while (stack.peek() != '[') {
temp.append(stack.pop());
}
// 解析完毕
len = Integer.parseInt(temp.toString());
// 解析中括号
StringBuilder sub = new StringBuilder();
while (true) {
Character template = stack.peek();
if (template == '[') {
stackB.push(stack.pop());
if (stackB.size() > 1) sub.append(template);
} else if (template == ']') {
if (stackB.size() > 1) sub.append(template);
stackB.pop();
stack.pop();
if (stackB.empty()) {
result = decodeString(sub.toString());
if (result == null) result = "";
break;
}
} else {
sub.append(stack.pop());
}
}
stringBuilder.append(result.repeat(len));
}
}
return stringBuilder.toString();
}
static class MyQueue {
Stack<Character> stackA = new Stack<>();
Stack<Character> stackB = new Stack<>();
public MyQueue() {
}
public void push(Character x) {
stackA.push(x);
}
public Character pop() {
if (stackB.empty()) {
while (!stackA.empty()) {
stackB.push(stackA.pop());
}
}
return stackB.pop();
}
public Character peek() {
if (stackB.empty()) {
while (!stackA.empty()) {
stackB.push(stackA.pop());
}
}
return stackB.peek();
}
public boolean empty() {
return stackA.empty() && stackB.empty();
}
}
}
}