タイトル#
エンコードされた文字列が与えられた場合、デコードされた文字列を返します。
エンコードルールは、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();
}
}
}
}