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

其他系列文章导航

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)
}