【数据结构和算法】字符串解码

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

---

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

2.1 什么情况会用到栈

2.2 方法一：辅助栈法

三、代码

3.1 方法一：辅助栈法

四、复杂度分析

4.1 方法一：辅助栈法

---

前言

这是力扣的 394 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。

慢慢开始栈的模块了，这道题是一道非常好的栈的例题，很有代表性。

---

一、题目描述

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

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

---

二、题解

2.1 什么情况会用到栈

栈是一种数据结构，其特点是后进先出（Last In First Out，LIFO）。在算法中，栈在很多情况下是非常有用的，下面是一些常见的情况：

• 括号匹配：当你有一个包含括号的字符串，并且你想要检查这个字符串中的括号是否匹配，你可以使用栈。从左到右扫描字符串，如果遇到左括号（如“(”，“{”或“[”），则将其压入栈。如果遇到右括号，则从栈顶弹出一个元素并检查它们是否匹配。如果它们不匹配，那么这个字符串就不是有效的。
• 深度优先搜索（DFS）：在图的遍历中，栈经常被用于实现深度优先搜索。首先，将起始节点压入栈。然后，当栈不为空时，弹出栈顶元素并访问它。对于每个刚刚访问过的节点，将其未被访问过的邻居节点压入栈。
• 函数调用：在计算机程序的执行中，函数调用通常使用栈来管理。当一个函数被调用时，它的参数和局部变量被压入栈。当函数执行结束时，这些数据从栈中弹出。
• 文本编辑器中的撤销/重做功能：许多文本编辑器使用撤销/重做功能来允许用户撤销他们最近所做的更改。这些功能通常使用一个操作栈，每个操作（例如插入或删除文本）都被压入栈。用户可以多次撤销，每次撤销都从栈中弹出并反转一个操作。
• 解析语法：在编译原理中，栈被广泛用于解析语法。例如，在解析一个算术表达式时，你可以使用栈来保持追踪括号和操作符的优先级。

这只是栈在算法中的一些应用，实际上还有很多其他的应用场景。

2.2 方法一：辅助栈法

本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

思路与算法：

本题用到两个辅助栈：???????一个存次数，一个存字母

?

构建辅助栈 stack， 遍历字符串 s 中每个字符 c；

• 当 c 为数字时，将数字字符转化为数字 cnt ，用于后续倍数计算；
• 当 c 为字母时，在 sb 尾部添加 c；
• 当 c 为 [ 时，将当前 cnt 和 sb 入栈，并分别置空置 0：

记录此 [ 前的临时结果 sb 至栈，用于发现对应 ] 后的拼接操作；

记录此 [ 前的倍数 cnt 至栈，用于发现对应 ] 后，获取 cnt × [...] 字符串。

进入到新 [ 后，sb 和 cnt 重新记录。

当 c 为 ] 时，stack 出栈，拼接字符串 sb = last_sb? + cntNow * sb，其中:

• last_sb 是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a；
• cntNow 是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。

返回字符串 sb 。

---

三、代码

3.1 方法一：辅助栈法

Java版本：

class Solution {
    public String decodeString(String s) {
      StringBuilder sb = new StringBuilder();
        int cnt = 0;
        LinkedList<Integer> n = new LinkedList<>();
        LinkedList<String> str = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == '[') {
                n.addLast(cnt);
                str.addLast(sb.toString());
                cnt = 0;
                sb = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                Integer cntNow = n.removeLast();
                for (int i = 0; i < cntNow; i++) tmp.append(sb);
                sb = new StringBuilder(str.removeLast() + tmp);
            } else if (c >= '0' && c <= '9') {
                cnt = cnt * 10 + Integer.parseInt(String.valueOf(c));
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

C++版本：

class Solution {
public:
    std::string decodeString(std::string s) {
        std::stack<int> counts;
        std::stack<std::string> strings;
        std::string result;
        int count = 0;
        for (char c : s) {
            if (c == '[') {
                counts.push(count);
                count = 0;
                strings.push(result);
                result = "";
            } else if (c == ']') {
                std::string temp = result;
                result = strings.top();
                strings.pop();
                int repeatCount = counts.top();
                counts.pop();
                for (int i = 0; i < repeatCount; i++) {
                    result += temp;
                }
            } else if (std::isdigit(c)) {
                count = count * 10 + (c - '0');
            } else {
                result += c;
            }
        }
        return result;
    }
};

Python版本：

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for char in s:
            if char == ']':
                tmp = ""
                while stack[-1] != "[":
                    tmp = stack.pop() + tmp
                stack.pop()  # remove '['
                k = ""
                while stack and stack[-1].isdigit():
                    k = stack.pop() + k
                stack.append(tmp * int(k))
            else:
                stack.append(char)

        return "".join(stack)

Go版本：

package main

import (
    "fmt"
    "strconv"
    "unicode"
)

func decodeString(s string) string {
    stack := []string{}

    for _, char := range s {
        if char == ']' {
            tmp := ""
            for stack[len(stack)-1] != "[" {
                lastIdx := len(stack) - 1
                tmp = stack[lastIdx] + tmp
                stack = stack[:lastIdx]
            }
            stack = stack[:len(stack)-1] // remove '['
            k := ""
            for len(stack) > 0 && unicode.IsDigit(rune(stack[len(stack)-1][0])) {
                lastIdx := len(stack) - 1
                k = stack[lastIdx] + k
                stack = stack[:lastIdx]
            }

            n, _ := strconv.Atoi(k)
            newStr := ""
            for i := 0; i < n; i++ {
                newStr += tmp
            }
            stack = append(stack, newStr)
        } else {
            stack = append(stack, string(char))
        }
    }

    return fmt.Sprint(stack)
}

func main() {
    s := "3[a]2[bc]"
    result := decodeString(s)
    fmt.Println(result)
}

---

四、复杂度分析

4.1 方法一：辅助栈法

• 时间复杂度?O(N)，一次遍历?s；
• 空间复杂度?O(N)，辅助栈在极端情况下需要线性空间，例如?2[2[2[a]]]。

---