Title#
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there will be no extra spaces, and the square brackets will always be formatted correctly.
In addition, you may assume that the original data does not contain any numbers, and that all numbers only represent the repetition count k. For example, there won't be input like 3a or 2[4].
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Solution:#
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) {
// Push into stack
MyQueue stack = new MyQueue();
// Bracket parsing stack
Stack<Character> stackB = new Stack<>();
for (int i = 0; i < s.length(); i++) {
stack.push(s.charAt(i));
}
StringBuilder stringBuilder = new StringBuilder();
// Take letters one by one and determine
// 1. Letters: append to the string
// 2. Numbers: parse the number, recursively pass the characters inside the brackets to the function for parsing, and multiply the result by the number
String result = null;
int len = 0;
while (!stack.empty()) {
// Append letters to the string
if (!Character.isDigit(stack.peek())) {
stringBuilder.append(stack.pop());
} else {
// Parse the number
StringBuilder temp = new StringBuilder();
while (stack.peek() != '[') {
temp.append(stack.pop());
}
// Parsing is complete
len = Integer.parseInt(temp.toString());
// Parse the brackets
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();
}
}
}
}
This article is synchronized to xLog by Mix Space.
The original link is https://me.liuyaowen.club/notes/1