题解 | JAVA #字符串解码# [P3]

Deque + regex Matcher

import java.util.regex.Matcher;
import java.util.regex.Pattern;

import java.util.*;

public class Solution {

    public String decodeString (String s) {
      if (s.isEmpty()) return "";
      
      Deque<Character> stack = new ArrayDeque<>();
      for (char c : s.toCharArray()) {
        stack.push(c);
        if (c == ']')  {
          StringBuilder sb = new StringBuilder();
          while (stack.peek() != '[') {
            sb.append(stack.pop()); // pop ']' and word
          }
          sb.append(stack.pop());   // pop '['
          while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
            sb.append(stack.pop()); // pop k
          }
          // at this point, sb stores the reversed of k[word]
          String decoded = decodeBasic(sb.reverse().toString());
          for (char d : decoded.toCharArray()) {
            stack.push(d);
          }
        }
      }
      
      StringBuilder ans = new StringBuilder();
      while (!stack.isEmpty()) {
        // Deque当栈用的时候push/pop都在first, 所以栈底是last.
        ans.append(stack.pollLast());
      }
      return ans.toString();
    }
  
    // Decode unnested %d[%s]
    public String decodeBasic(String s) {
      Pattern p = Pattern.compile("(\\d+)\\[([a-zA-Z]+)\\]");
      Matcher m = p.matcher(s);
      m.find();
      int k = Integer.valueOf(m.group(1));
      String c = m.group(2);
      
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < k; i++) {
        sb.append(c);
      }
      return sb.toString();
    }
}