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 being 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, square brackets are well-formed, and the input string contains only lowercase English letters.
Additionally, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, 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();
// Stack for parsing square brackets
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 check
// 1. If it's a letter, append it to the string
// 2. If it's a number, parse the number and recursively parse the characters inside the square brackets, then 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 completed
len = Integer.parseInt(temp.toString());
// Parse the square 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