LeetCode 热题 100_字符串解码（71_394_中等_C++）（栈）

题目描述：

给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: 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]

题解：

解题思路：

思路一（栈）：

1、通过中括号内嵌中括号的情况，且内嵌的中括号首先计算，可以想到栈的方法解决此问题。 字符串中有四种字符： ① 数字：将数字转换为整数（数字的位数可为多位），称为字符串的重复次数 ② 字母：将连续的字母提取出来，连接成字符串 ③ 左括号：重复次数和字符串 分别入 数字栈和字符串栈 ④ 右括号：弹出状态（出栈），重复n次对应字符串，并连接字符串 例子 ：s = “3[a2[c]]” 初始状态：k=0 (数字), current=“” (部分字符串), counts栈为空，strings栈为空 ① 3 为数字字符，计算连续的数字字符并转换为整数，k=3; ② [ 为左括号，将k=3 和 current=““分别压入 counts栈={3}和strings={””}栈，重置k=0，current=“” ③ a 为字母,计算连接的字母,current=“a”; ④ 2 k=2; ⑤ [ 将k=2 和 current=“a” 分别压入 counts栈={3,2}和strings栈={“”,“a”}，重置k=0，current=“” ⑥ c current=“c”; ⑦ ] 遇到右括号，将counts栈={3,2}中的2出栈，此时current=“c"重复2次 -> current=“cc”,strings栈={”“,“a”}中的"a"出栈,与current连接"acc” ⑧ ] 遇到右括号，counts栈={3}中的3出栈，此时current=“acc"重复3次->current = “accaccacc”,strings栈={”“}中的”“出栈,与current连接"accaccacc” 2、复杂度分析： ① 时间复杂度： O(S)，S代表解码后得出的字符串长度，我们在遍历原字符串的同时会也会将解码后的字符串压入栈中，且进行字符串的连接。 ② 空间复杂度：O(S)，S代表解码后得出的字符串长度，栈的总大小最终与 S 相同。

代码实现

代码实现（栈）：

class Solution { public: string decodeString(string s) { stack counts; // 用来存储数字 (重复次数)，栈用来存储每个 “[” 对应的重复次数 stack strings; // 用来存储之前的部分字符串，栈用来存储每个 “[” 之前的字符串 string current = “”; // 用来存储当前正在构建的字符串（用于存放当前解析出来的子字符串） int k = 0; // 用来存储当前的重复次数 // 遍历字符串中的每个字符 for (char c : s) { if (isdigit(c)) { // 如果是数字，构建重复次数 k，直到遇到非数字字符 k = k * 10 + (c - ‘0’); // 处理可能多位的数字 } else if (c == ‘[’) { // 如果遇到 ‘[’，说明要开始一个新的子字符串块 counts.push(k); // 将当前的重复次数推入栈中 strings.push(current); // 将当前构建的字符串推入栈中 current = “”; // 清空当前字符串，准备构建新的子字符串 k = 0; // 重置重复次数为 0，开始处理新的重复数字 } else if (c == ‘]’) { // 如果遇到 ‘]’，说明当前子字符串块的解析结束 string temp = current; // 将当前的字符串保存到 temp 中 current = strings.top(); // 从栈中获取之前的字符串部分 strings.pop(); // 弹出栈中的字符串部分 int repeatCount = counts.top(); // 从栈中获取重复次数 counts.pop(); // 弹出栈中的重复次数 // 将当前子字符串重复 repeatCount 次，并拼接到之前的部分 for (int i = 0; i < repeatCount; i++) { current += temp; // 重复并拼接 } } else { // 普通字符，直接加入当前正在构建的字符串 current += c; } } return current; // 返回解码后的最终字符串 } };

以思路一为例进行调试

#include #include using namespace std; class Solution { public: string decodeString(string s) { stack counts; // 用来存储数字 (重复次数)，栈用来存储每个 “[” 对应的重复次数 stack strings; // 用来存储之前的部分字符串，栈用来存储每个 “[” 之前的字符串 string current = “”; // 用来存储当前正在构建的字符串（用于存放当前解析出来的子字符串） int k = 0; // 用来存储当前的重复次数 // 遍历字符串中的每个字符 for (char c : s) { if (isdigit(c)) { // 如果是数字，构建重复次数 k，直到遇到非数字字符 k = k * 10 + (c - ‘0’); // 处理可能多位的数字 } else if (c == ‘[’) { // 如果遇到 ‘[’，说明要开始一个新的子字符串块 counts.push(k); // 将当前的重复次数推入栈中 strings.push(current); // 将当前构建的字符串推入栈中 current = “”; // 清空当前字符串，准备构建新的子字符串 k = 0; // 重置重复次数为 0，开始处理新的重复数字 } else if (c == ‘]’) { // 如果遇到 ‘]’，说明当前子字符串块的解析结束 string temp = current; // 将当前的字符串保存到 temp 中 current = strings.top(); // 从栈中获取之前的字符串部分 strings.pop(); // 弹出栈中的字符串部分 int repeatCount = counts.top(); // 从栈中获取重复次数 counts.pop(); // 弹出栈中的重复次数 // 将当前子字符串重复 repeatCount 次，并拼接到之前的部分 for (int i = 0; i < repeatCount; i++) { current += temp; // 重复并拼接 } } else { // 普通字符，直接加入当前正在构建的字符串 current += c; } } return current; // 返回解码后的最终字符串 } }; int main(int argc, char const *argv[]) { string str=“3[a2[c]]”; Solution s; string ans=s.decodeString(str); cout«ans; return 0; } [LeetCode 热题 100_字符串解码（71_394)原题链接](https://leetcode.cn/problems/decode- string/description/?envType=study-plan-v2&envId=top-100-liked) 欢迎大家和我沟通交流(✿◠‿◠)