Question

394. 字符串解码

English Version

题目描述

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

编码规则为: 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"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

 

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300] 

解法

方法一

class Solution:
  def decodeString(self, s: str) -> str:
    s1, s2 = [], []
    num, res = 0, ''
    for c in s:
      if c.isdigit():
        num = num * 10 + int(c)
      elif c == '[':
        s1.append(num)
        s2.append(res)
        num, res = 0, ''
      elif c == ']':
        res = s2.pop() + res * s1.pop()
      else:
        res += c
    return res

class Solution {
  public String decodeString(String s) {
    Deque<Integer> s1 = new ArrayDeque<>();
    Deque<String> s2 = new ArrayDeque<>();
    int num = 0;
    String res = "";
    for (char c : s.toCharArray()) {
      if ('0' <= c && c <= '9') {
        num = num * 10 + c - '0';
      } else if (c == '[') {
        s1.push(num);
        s2.push(res);
        num = 0;
        res = "";
      } else if (c == ']') {
        StringBuilder t = new StringBuilder();
        for (int i = 0, n = s1.pop(); i < n; ++i) {
          t.append(res);
        }
        res = s2.pop() + t.toString();
      } else {
        res += String.valueOf(c);
      }
    }
    return res;
  }
}

function decodeString(s: string): string {
  let ans = '';
  let stack = [];
  let count = 0; // repeatCount
  for (let cur of s) {
    if (/[0-9]/.test(cur)) {
      count = count * 10 + Number(cur);
    } else if (/[a-z]/.test(cur)) {
      ans += cur;
    } else if ('[' == cur) {
      stack.push([ans, count]);
      // reset
      ans = '';
      count = 0;
    } else {
      // match ']'
      let [pre, count] = stack.pop();
      ans = pre + ans.repeat(count);
    }
  }
  return ans;
}