字符串解码 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

前言

首先明确输入的 $s$ 有哪些类型：

基础：不含括号，所以也没有数字，此时 $s$ 只包含字母，例如 $s = abc$ 。
嵌套：如题目所说，k[encoded_string]，即数字 + 左括号 + 括号中的字符串 + 右括号。
- 例如 $s = 2[abc]$ ，解码后是 $abcabc$ 。
- 例如 $s = 2[3[ab]]$ ，内层的 $3[ab] = ababab$ ，所以 $2[3[ab]] = 2[ababab] = abababababab$ 。
组合：多个 k[encoded_string] 并在一起。
- 例如 $s = 2[ab]3[xy] = 2[ab] + 3[xy] = abab + xyxyxy = ababxyxyxy$ 。
- 例如 $s = ab2[cd]e = ab + 2[cd] + e = ab + cdcd + e = abcdcde$ 。

第一种递归写法

分类讨论：

如果 $s$ 是空串，返回空串。
如果 $s_{0}$ 是字母，我们可以递归解码 $s_{1}$ 到 $s_{n - 1}$ 。
- 如果 $s$ 是基础类型，例如 $s = abc$ ，那么 $a + bc$ 仍然是 $abc$ 。
- 如果 $s$ 是组合类型，例如 $s = ab2[cd]e$ ，那么答案等于 $a + b2[cd]e$ ，后者可以继续递归解码。
否则， $s_{0}$ 一定是数字。这意味着 $s$ 至少包含一对括号。
- 找第一个左括号的下标 $i$ 。
- 找与 $s_{i}$ 匹配的右括号的下标 $j$ 。⚠注意：对于 $s = 2[3[ab]]$ 这种嵌套类型，我们需要跳过内层的括号。可以用一个变量 $balance$ 表示左括号减去右括号的个数，在遍历 $s$ 的过程中维护 $balance$ ，一旦 $balance = 0$ 就表示我们找到了与第一个左括号匹配的右括号。
- 把 $s$ 分成三部分：
  - $s_{0}$ 到 $s_{i - 1}$ 转成数字 $k$ 。
  - $s_{i + 1}$ 到 $s_{j - 1}$ 继续递归解码，得到字符串 $a$ 。
  - $s_{j + 1}$ 到 $s_{n - 1}$ 继续递归解码，得到字符串 $b$ 。
- 把 $a$ 重复 $k$ 次，再与 $b$ 拼接，得到答案 $a \cdot k + b$ 。

Python 解法1C++ 解法1

python

class Solution:
    def decodeString(self, s: str) -> str:
        if not s:
            return s

        # s[0] 是字母
        if s[0].isalpha():
            # 分离出 s[0]，解码剩下的
            return s[0] + self.decodeString(s[1:])

        # s[0] 是数字，后面至少有一对括号
        i = s.find('[')  # 找左括号
        # 找右括号，注意对于 [...[...]...] 这种情况，第一个右括号并不是我们要找的，第二个才是
        balance = 1  # 左括号个数减去右括号个数
        for j in count(i + 1):  # 从 i+1 开始向右遍历，找与 s[i] 匹配的右括号
            if s[j] == '[':
                balance += 1
            elif s[j] == ']':
                balance -= 1
                if balance == 0:  # 左右括号个数相等，找到与 s[i] 匹配的右括号 s[j]
                    return self.decodeString(s[i + 1: j]) * int(s[:i]) + self.decodeString(s[j + 1:])

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    string decodeString(string s) {
        if (s.empty()) {
            return s;
        }

        // s[0] 是字母
        if (isalpha(s[0])) {
            // 分离出 s[0]，解码剩下的
            return s[0] + decodeString(s.substr(1));
        }

        // s[0] 是数字，后面至少有一对括号
        int i = s.find('['); // 找左括号
        // 找右括号，注意对于 [...[...]...] 这种情况，第一个右括号并不是我们要找的，第二个才是
        int balance = 1; // 左括号个数减去右括号个数
        for (int j = i + 1; ; j++) {
            if (s[j] == '[') {
                balance++;
            } else if (s[j] == ']') {
                balance--;
                if (balance == 0) { // 左右括号个数相等，找到与 s[i] 匹配的右括号 s[j]
                    int k = stoi(s.substr(0, i));
                    string t = decodeString(s.substr(i + 1, j - i - 1));
                    string res;
                    while (k--) {
                        res += t;
                    }
                    return res + decodeString(s.substr(j + 1));
                }
            }
        }
    }
};

复杂度分析

时间复杂度： $O (U^{m})$ ，其中 $U \leq 300$ 为 $k$ 的最大值， $m = O (\frac{n}{\log U})$ ， $n$ 是 $s$ 的长度。最坏情况下 $s$ 形如 $300[300[...[300[a]]...]]$ ，嵌套 $m = O (\frac{n}{\log U})$ 层，生成的字符串长度为 $300 \times 300 \times \dots \times 300 = 300^{m}$ 。不过，本题保证答案长度不超过 $10^{5}$ 。
空间复杂度： $O (U^{m})$ 。

第二种递归写法

把 $s$ 视作若干基础字符串和 k[encoded_string] 的并。

以 $s = ab2[cd]3[e]$ 为例说明，将其视作 $ab + 2[cd] + 3[e]$ 。从左到右遍历 $s$ ：

$s_{0} = a$ ，加到答案中，现在答案为 $a$ 。
$s_{1} = b$ ，加到答案中，现在答案为 $ab$ 。
$s_{2} = 2$ ，更新重复次数 $k = 2$ 。
$s_{3} = [$ ，往下递归。
$s_{4} = c$ ，在下一级递归函数中的字符串为 $c$ 。
$s_{5} = d$ ，在下一级递归函数中的字符串为 $cd$ 。
$s_{6} =]$ ，递归返回 $cd$ 。上层递归函数接收到 $cd$ ，将其重复 $k = 2$ 次，得到 $cdcd$ ，加到答案中，现在答案为 $abcdcd$ 。然后重置 $k = 0$ 。⚠注意：如果不重置，后面遍历到数字 $3$ 的时候，会把 $3$ 加到 $2$ 的后面，得到错误的 $k = 23$ 。
$s_{7} = 3$ ，更新重复次数 $k = 3$ 。
$s_{8, 9, 10} = [e]$ ，和上面一样，递归，得到字符串 $e$ 。将其重复 $k = 3$ 次，得到 $eee$ ，加到答案中，最终答案为 $abcdcdeee$ 。

细节

问：递归过程中，怎么知道当前遍历到哪个字符了？

答：可以用一个在递归函数外的变量 $i$ 表示当前下标，每遍历到一个字符，就把 $i$ 加一。

问：如果 $s = 123[a]$ ，怎么把字符串 $123$ 变成数字 $k = 123$ ？

答：利用式子 $k = k \cdot 10 + int (s_{i})$ 计算。

初始化 $k = 0$ 。
更新 $k$ 为 $k \cdot 10 + 1 = 0 + 1 = 1$ 。
更新 $k$ 为 $k \cdot 10 + 2 = 10 + 2 = 12$ 。
更新 $k$ 为 $k \cdot 10 + 3 = 120 + 3 = 123$ 。

Python 解法3C++ 解法3

python

class Solution:
    def decodeString(self, s: str) -> str:
        i = 0

        def decode() -> str:
            nonlocal i
            res = ''  # 或者 res = []，具体见另一份代码【Python3 列表】
            k = 0
            while i < len(s):
                c = s[i]
                i += 1
                if c.isalpha():
                    res += c
                elif c.isdigit():
                    k = k * 10 + int(c)
                elif c == '[':  # 递
                    res += decode() * k  # 把括号内的字符串重复 k 次
                    k = 0  # 重置 k，若不重置，2[a]3[b] 后面的 3 会算出 k = 23
                else:  # ']' 归
                    break
            return res

        return decode()

cpp

// C++ 版待补充

Python 解法4C++ 解法4

python

class Solution:
    def decodeString(self, s: str) -> str:
        i = 0

        def decode() -> str:
            nonlocal i
            res = []
            k = 0
            while i < len(s):
                c = s[i]
                i += 1
                if c.isalpha():
                    res.append(c)
                elif c.isdigit():
                    k = k * 10 + int(c)
                elif c == '[':  # 递
                    res.append(decode() * k)  # 把括号内的字符串重复 k 次
                    k = 0  # 重置 k，若不重置，2[a]3[b] 后面的 3 会算出 k = 23
                else:  # ']' 归
                    break
            return ''.join(res)

        return decode()

cpp

// C++ 版待补充

C++ 解法5

cpp

class Solution {
public:
    string decodeString(string s) {
        int i = 0;

        auto decode = [&](this auto&& decode) -> string {
            string res;
            int k = 0;
            while (i < s.size()) {
                char c = s[i];
                i++;
                if (isalpha(c)) {
                    res += c;
                } else if (isdigit(c)) {
                    k = k * 10 + (c - '0');
                } else if (c == '[') { // 递
                    string t = decode();
                    for (; k > 0; k--) {
                        res += t; // 把括号内的字符串重复 k 次
                    }
                } else { // ']' 归
                    break;
                }
            }
            return res;
        };

        return decode();
    }
};

复杂度分析

时间复杂度： $O (U^{m})$ ，理由同上。注意生成的字符串有多长，就需要多少的时间。不过，本题保证答案长度不超过 $10^{5}$ 。
空间复杂度： $O (U^{m})$ 。

用栈模拟递归

把第二种递归改写成非递归写法。

首先你要理解计算机底层是如何实现递归的，请看视频深刻理解递归【基础算法精讲 09】。

简单来说，在往下「递」的时候，计算机会把当前函数中的局部变量保存到栈中；下层递归函数「归」之后，再从栈中把保存的变量取出。我们可以手动模拟这个过程，具体实现如下。

Python 解法6C++ 解法6

python

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []  # 用于模拟计算机的递归
        res = ''
        k = 0
        for c in s:
            if c.isalpha():
                res += c
            elif c.isdigit():
                k = k * 10 + int(c)
            elif c == '[':
                # 模拟递归
                # 在递归之前，把当前递归函数中的局部变量 res 和 k 保存到栈中
                stack.append((res, k))
                # 递归，初始化 res 和 k
                res = ''
                k = 0
            else:  # ']'
                # 递归结束，从栈中恢复递归之前保存的局部变量
                pre_res, pre_k = stack.pop()
                # 此时 res 是下层递归的返回值，将其重复 pre_k 次，拼接到递归前的 pre_res 之后
                res = pre_res + res * pre_k
        return res

cpp

// C++ 版待补充

C++ 解法7

cpp

class Solution {
public:
    string decodeString(string s) {
        stack<pair<string, int>> stk; // 用于模拟计算机的递归
        string res;
        int k = 0;
        for (char c : s) {
            if (isalpha(c)) {
                res += c;
            } else if (isdigit(c)) {
                k = k * 10 + (c - '0');
            } else if (c == '[') {
                // 模拟递归
                // 在递归之前，把当前递归函数中的局部变量 res 和 k 保存到栈中
                stk.emplace(move(res), k);
                // 递归，初始化 res 和 k（由于 move 了，res 此时为空）
                k = 0;
            } else { // ']'
                // 递归结束，从栈中恢复递归之前保存的局部变量
                auto [pre_res, pre_k] = stk.top();
                stk.pop();
                // 此时 res 是下层递归的返回值，将其重复 pre_k 次，拼接到递归前的 pre_res 之后
                while (pre_k--) {
                    pre_res += res;
                }
                res = move(pre_res);
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O (U^{m})$ ，理由同上。注意生成的字符串有多长，就需要多少的时间。不过，本题保证答案长度不超过 $10^{5}$ 。
空间复杂度： $O (U^{m})$ 。

相似题目

1190. 反转每对括号间的子串

专题训练

见下面数据结构题单的「§3.5 表达式解析」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

前言 ​

第一种递归写法 ​

复杂度分析 ​

第二种递归写法 ​

细节 ​

复杂度分析 ​

用栈模拟递归 ​

复杂度分析 ​

相似题目 ​

专题训练 ​

分类题单 ​

前言

第一种递归写法

复杂度分析

第二种递归写法

细节

复杂度分析

用栈模拟递归

复杂度分析

相似题目

专题训练

分类题单