0394. 字符串解码【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 栈

1. 📝 题目描述

• leetcode

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

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 10^5。

---

示例 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]

2. 🎯 s.1 - 栈

c

char* decodeString(char* s) {
    int len = strlen(s);
    int numStack[100], numTop = 0;
    char* strStack[100];
    int strTop = 0;
    char* cur = (char*)calloc(10000, 1);
    int num = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            num = num * 10 + (s[i] - '0');
        } else if (s[i] == '[') {
            numStack[numTop++] = num;
            strStack[strTop++] = cur;
            cur = (char*)calloc(10000, 1);
            num = 0;
        } else if (s[i] == ']') {
            int repeat = numStack[--numTop];
            char* prev = strStack[--strTop];
            char* tmp = (char*)calloc(10000, 1);
            strcpy(tmp, prev);
            for (int j = 0; j < repeat; j++) strcat(tmp, cur);
            free(cur);
            cur = tmp;
        } else {
            int cl = strlen(cur);
            cur[cl] = s[i];
            cur[cl + 1] = '\0';
        }
    }
    return cur;
}

js

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  const numStack = [],
    strStack = []
  let cur = '',
    num = 0
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch - '0')
    } else if (ch === '[') {
      numStack.push(num)
      strStack.push(cur)
      num = 0
      cur = ''
    } else if (ch === ']') {
      cur = strStack.pop() + cur.repeat(numStack.pop())
    } else {
      cur += ch
    }
  }
  return cur
}

py

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

• 时间复杂度：$O(S)$，其中 $S$ 是解码后字符串长度
• 空间复杂度：$O(S)$

算法思路：

• 维护数字栈和字符串栈
• 遇 [ 时把当前数字和字符串压栈，遇 ] 时弹栈并重复拼接