力扣最热一百题——字符串解码

🕗 发布于 2024-11-12 23:28 算法 leetcode 栈蓝桥杯递归

题目链接：394. 字符串解码 - 力扣（LeetCode）

题目描述

题目链接：394. 字符串解码 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

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

解法一：双栈

`isDigit(c)`

在 Java 中，.isDigit(c) 是 Character 类中的一个静态方法，用于判断字符 c 是否是数字字符（即 0-9）。

用法

Character.isDigit(char c)

参数：接受一个字符 c。
返回值：返回 true 如果字符 c 是数字，否则返回 false。

示例

char c1 = '3';
char c2 = 'a';

System.out.println(Character.isDigit(c1)); // 输出 true，因为 '3' 是数字
System.out.println(Character.isDigit(c2)); // 输出 false，因为 'a' 不是数字

在解码字符串的代码中，用 .isDigit(c) 来检测当前字符是否为数字，从而区分出需要提取的重复次数。

Java写法：

class Solution {
    public String decodeString(String s) {
        // 存储倍数的栈
        Stack<Integer> stackNum = new Stack<>();  
        // 存储当前构建的字符串的栈  
        Stack<StringBuilder> stackStr = new Stack<>(); 

        StringBuilder currentStr = new StringBuilder();

        // 当前倍数
        int currentNum = 0;

        for (char c : s.toCharArray()) {
            // 判断是否是数字
            if (Character.isDigit(c)) {
                // 如果是数字，更新当前倍数
                currentNum = currentNum * 10 + (c - '0');
            } else if (c == '[') {
                // 遇到 '[' 时，将当前倍数和字符串存入栈
                stackNum.push(currentNum);
                stackStr.push(currentStr);
                // 重置 currentNum 和 currentStr
                currentNum = 0;
                currentStr = new StringBuilder();
            } else if (c == ']') {
                // 遇到 ']' 时，弹出栈顶倍数和字符串，将当前字符串重复并连接
                int num = stackNum.pop();
                StringBuilder prevStr = stackStr.pop();
                for (int i = 0; i < num; i++) {
                    prevStr.append(currentStr);
                }
                currentStr = prevStr;
            } else {
                // 普通字符直接追加到当前字符串
                currentStr.append(c);
            }
        }

        return currentStr.toString();
    }
}

C++写法：

#include <stack>
#include <string>
#include <sstream>

class Solution {
public:
    std::string decodeString(const std::string& s) {
        std::stack<int> stackNum;                // 存储倍数的栈
        std::stack<std::string> stackStr;        // 存储当前构建的字符串的栈
        std::string currentStr;                  // 当前字符串
        int currentNum = 0;                      // 当前倍数

        for (char c : s) {
            if (isdigit(c)) { // 判断是否是数字
                currentNum = currentNum * 10 + (c - '0'); // 更新当前倍数
            } else if (c == '[') {
                // 遇到 '[' 时，将当前倍数和字符串存入栈
                stackNum.push(currentNum);
                stackStr.push(currentStr);
                // 重置 currentNum 和 currentStr
                currentNum = 0;
                currentStr.clear();
            } else if (c == ']') {
                // 遇到 ']' 时，弹出栈顶倍数和字符串，将当前字符串重复并连接
                int num = stackNum.top(); stackNum.pop();
                std::string prevStr = stackStr.top(); stackStr.pop();
                for (int i = 0; i < num; i++) {
                    prevStr += currentStr;
                }
                currentStr = prevStr;
            } else {
                // 普通字符直接追加到当前字符串
                currentStr += c;
            }
        }

        return currentStr;
    }
};

运行时间

时间复杂度和空间复杂度

时间复杂度：O(n)
- 每个字符只被处理一次，且在遇到 [ 和 ] 时执行的操作也只需将栈顶元素出栈、入栈或进行简单的字符串拼接，时间复杂度是线性的。
- 由于没有嵌套层次的额外开销，每次处理的字符也不会重复。
空间复杂度：O(d + m)
- d 是嵌套深度（即 [ 和 ] 的深度），用于存储倍数和子字符串的栈。
- m 是存储当前构建字符串的空间，随输出增长而增加

解法二：递归

1. 定义递归处理的思路

递归函数在解码字符串的过程中，遇到 k[...] 形式的嵌套结构时，就会进入到更深一层的递归来处理 [...] 中的内容。最终将各个嵌套的部分逐一解码完成。

2. 实现步骤

初始化和循环解析：在递归函数中，初始化一个 result 变量，用于存储当前层次解码的结果。通过 while 循环逐字符解析，直到字符串结束或遇到 ] 为止。
解析倍数：当遇到数字字符时，将其解析为一个整数 k，表示接下来要重复的次数。可以通过多次读取字符来获得完整的 k 值（例如，对于 23[a]，读取到 23 作为倍数）。接着，跳过 [，进入递归，开始处理括号内的内容。
递归处理括号内的内容：调用递归函数处理括号内的部分。在递归调用结束后，函数会返回括号内解码后的子字符串。此时，将该子字符串重复 k 次，并将重复的结果拼接到当前层的 result 中。
遇到 ] 返回当前层的结果：当遇到 ] 时，说明当前层的解码结束，返回当前层的 result，使上层能够接收到并使用这个结果。
拼接普通字符：如果遇到普通字符，直接将其追加到 result 中，继续处理下一个字符。

示例

以 3[a2[c]] 为例，逐步解读递归的处理过程：

初始调用：decodeString(3[a2[c]])，index 初始化为 0，解析 3 作为倍数，然后跳过 [。
递归进入 a2[c] 部分：
- 解析到 a，直接加入 result 中。
- 遇到 2，解析出倍数 2，并进入递归，处理 c。
递归处理 c：
- 返回 c，上层将其重复 2 次，得到 cc，将其与之前的 a 拼接，得到 acc。
返回并处理倍数 3：回到初始层，重复 acc 三次得到 accaccacc，完成解码。

代码中的关键点

每次进入递归时，能够解码一个新的嵌套部分。
遇到 ] 时，返回当前层的结果，使得解码在嵌套中逐层展开和拼接。

Java写法：

class Solution {
    // 全局指针，用来记录当前解析的字符位置
    private int index = 0; 

    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();

        while (index < s.length()) {
            char c = s.charAt(index);

            // 如果是数字，解析出完整的数字作为重复次数
            if (Character.isDigit(c)) {
                int k = 0;
                while (Character.isDigit(s.charAt(index))) {
                    k = k * 10 + (s.charAt(index) - '0');
                    index++;
                }
                // 跳过 '['
                index++; 
                
                // 递归处理括号内的字符串
                String decoded = decodeString(s);
                
                // 将解码后的子串重复 k 次加入结果中
                for (int i = 0; i < k; i++) {
                    result.append(decoded);
                }
            } else if (c == ']') {
                // 碰到 ']'，返回当前层的结果
                index++; // 跳过 ']'
                return result.toString();
            } else {
                // 普通字符，直接加入结果
                result.append(c);
                index++;
            }
        }

        return result.toString();
    }
}

C++写法：

#include <string>

class Solution {
private:
    int index = 0;  // 全局指针，用来记录当前解析的字符位置

public:
    std::string decodeString(const std::string& s) {
        std::string result;

        while (index < s.length()) {
            char c = s[index];

            // 如果是数字，解析出完整的数字作为重复次数
            if (isdigit(c)) {
                int k = 0;
                while (isdigit(s[index])) {
                    k = k * 10 + (s[index] - '0');
                    index++;
                }
                // 跳过 '['
                index++; 

                // 递归处理括号内的字符串
                std::string decoded = decodeString(s);

                // 将解码后的子串重复 k 次加入结果中
                for (int i = 0; i < k; i++) {
                    result += decoded;
                }
            } else if (c == ']') {
                // 碰到 ']'，返回当前层的结果
                index++; // 跳过 ']'
                return result;
            } else {
                // 普通字符，直接加入结果
                result += c;
                index++;
            }
        }

        return result;
    }
};

运行时间

时间复杂度和空间复杂度

时间复杂度

假设输入字符串的长度为 n。

解析每个字符：递归方法会遍历字符串的每个字符一次。对于每个字符：
- 如果是普通字符，直接追加到当前的结果字符串，操作时间是 O(1)。
- 如果是数字字符，解析成倍数并进行递归处理。在遇到 [ 后进行递归时，每次递归都会处理相应嵌套的字符串。
重复字符串的拼接：当遇到 k[encoded_string] 结构时，解码后的 encoded_string 被重复 kkk 次，并拼接到结果中。最坏情况下，整个字符串可能包含多层嵌套或大量重复，因此整体的拼接时间可能达到 O(n×k)，其中 k 是所有倍数的最大值。例如，对于字符串 100[a]，解析后得到的结果是 a 重复 100次，需要 O(100)的拼接时间。

因此，总的时间复杂度为 O(n×k)，其中 n 是字符串的长度，k 是倍数的最大值。实际的复杂度取决于字符串的结构，特别是嵌套深度和重复次数的大小。

空间复杂度

空间复杂度取决于递归深度和临时存储的字符串大小。

递归深度：每次递归调用会将局部变量（如 index 和 result）存储在栈中，因此递归深度会影响空间复杂度。最坏情况下递归深度与嵌套的层数相同。如果嵌套层数为 ddd，则递归栈空间为 O(d)。
结果字符串的大小：由于需要构建最终解码的字符串，最坏情况下的解码结果长度可能达到 O(n×k)。

总结

问题描述 给定编码的字符串，解码规则为 k[encoded_string]，表示 encoded_string 重复 k 次，返回解码后的字符串。

解法一：双栈 通过一个栈保存倍数，另一个栈保存当前构建的字符串。在遍历字符串时：

若为数字，计算当前倍数。
若遇到 [，将当前倍数和字符串压入栈，并重置。
若遇到 ]，从栈中弹出倍数和前序字符串，将当前字符串按倍数重复并拼接。
若为普通字符，则直接添加至当前字符串。 时间复杂度：O(n)，每个字符只被处理一次。空间复杂度：O(d)，d为嵌套深度。

解法二：递归 使用递归解析嵌套结构，每次进入递归表示进入一个新的 k[...] 结构：

若为数字，则解析为倍数 k 并递归处理 [...] 部分。
遇到 ]，返回当前层的字符串。
普通字符直接添加到结果。 时间复杂度：O(n×k)，n 为字符串长度，k 为最大倍数。空间复杂度：O(d)，d 为嵌套层数。

总结

双栈：适合层次浅、字符串结构较简单的情况。
递归：处理嵌套层次深、复杂结构的字符串时更直观。

原文地址：https://blog.csdn.net/DDDDWJDDDD/article/details/143675013

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：力扣.167 两数之和 II two-sum-ii
下一篇：深入探讨Vue项目中缺少明显入口文件的原因及解决策略

学生公寓管理系统
由于某些特殊原因，需要对学生当前入住的床位进行修改时，使用此功能。新生开学后，宿管管理可以先根据学生所在系查询该专业预定的宿舍和具体的床位入住状态信息，为该学生分配一个空闲状态的床位，并修改当前床位状
阅读更多2024-11-15
Windows上安装RabbitMQ 4.0.3教程
通过上述步骤，你应该已经成功在Windows上安装了RabbitMQ 4.0.3，并启用了管理插件。现在，你可以开始使用RabbitMQ来构建你的分布式系统了。希望这篇教程对你有所帮助，如果有任何问题
阅读更多2024-11-15
【蓝桥等考C++真题】蓝桥杯等级考试C++组第13级L13真题原题(含答案)-成绩排序
C++L13 成绩排序(50 分)
阅读更多2024-11-15
Web入门
HTTP（HyperText Transfer Protocol，超文本传输协议）是一种应用层协议。主要用于在Web浏览器和服务器之间传输数据。基于TCP协议：面向连接，确保了数据传输的可靠性和顺序。
阅读更多2024-11-15
Android 最新的AndroidStudio引入依赖失败如何解决？如:Failed to resolve:xxxx
在引入依赖时报错：Failed to resolve: xxx.xxxx:1.1.0。
阅读更多2024-11-15
力扣113：路径总和II
力扣113：路径总和II。C语言
阅读更多2024-11-15
【springboot使用sqlite数据库】Java后台同时使用mysql、sqlite
根据业务的需要，老版程序使用的数据库是sqlite，版本升级成前后台分离模式，因此需要兼容mysql与sqlite数据库同时使用。
阅读更多2024-11-15
力扣.15 三数之和 three-sum
这道题作为 leetcode 的第 15 道题，看起来似曾相识。大概思路可以有下面几种：暴力解法数组排序+二分Hash 优化双指针。
阅读更多2024-11-15
力扣第 53 题：最大子数组和
题目给定一个整数数组nums，目标是找到和最大的连续子数组（最少包含一个元素），并返回其和。例如，在数组中，和最大的子数组为，其和为6。
阅读更多2024-11-15
linux-缓冲区
调用系统调用接口是需要时间成本的，如果使用缓冲区，存储的字符串到一定长度再调用系统调用，能够有效减少调用系统调用的次数。这个缓冲区是语言设置的，缓冲区满足条件就用系统调用接口write将缓冲区的内容刷
阅读更多2024-11-15

力扣最热一百题——字符串解码

题目链接：394. 字符串解码 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：双栈

isDigit(c)

用法

示例

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

解法二：递归

1. 定义递归处理的思路

2. 实现步骤

示例

代码中的关键点

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

时间复杂度

空间复杂度

总结

相关文章

`isDigit(c)`