题目

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: 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();
          }
      }
  }
}

LeetCode [394] 字符串解码

题目

解答：