LeetCode [394] 字串解碼

2024年8月20日#手记344

AI 翻譯

這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文

AI 生成的摘要

給定一個編碼字符串，要求返回解碼後的字符串。編碼格式為 `k[encoded_string]`，其中 `k` 為正整數，表示方括號內的 `encoded_string` 重複 `k` 次。輸入字符串總是有效，且不包含額外空格或不符合格式的方括號。示例： 1. 輸入：`"3[a]2[bc]"`，輸出：`"aaabcbc"` 2. 輸入：`"3[a2[c]]"`，輸出：`"accaccacc"` 3. 輸入：`"2[abc]3[cd]ef"`，輸出：`"abcabccdcdcdef"` 解題思路使用了堆疊結構來解析字符串，通過入栈和出栈的方式來處理編碼和解碼的過程。

題目#

給定一個經過編碼的字符串，返回它解碼後的字符串。

編碼規則為: 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

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