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();
          }
      }
  }
}

此文由 Mix Space 同步更新至 xLog
原始鏈接為 https://me.liuyaowen.club/notes/1