字符串解码(力扣 394)Java栈操作

简介: 给定一个经过编码的字符串,返回它解码后的字符串。

一、题目描述



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


编码规则为: 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、构建辅助栈 stack, 遍历字符串 s 中每个字符 c;


当 c 为数字时,将数字字符转化为数字 multi,用于后续倍数计算;

当 c 为字母时,在 res 尾部添加 c;

当 c 为 [ 时,将当前 multi 和 res 分别入数字栈和字符串栈,并分别置空置 0:

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

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

进入到新 [ 后,res 和 multi 重新记录。

当 c 为 ] 时,stack 出栈,拼接字符串 res = curr + count * res,其中:

curr是上个 [ 到当前 [ 的字符串,例如 "3[a2[c]]" 中的 a;

count是当前 [ 到 ] 内字符串的重复倍数,例如 "3[a2[c]]" 中的 2。


2、返回字符串 res。


三、Java代码实现



class Solution {
    public String decodeString(String s) {
        String res = "";  //作为最终结果的字符串
        Stack<Integer> stack_multi = new Stack<>(); //保存数字的栈
        Stack<String> stack_res = new Stack<>();  //保存字符串的栈
        int multi = 0;    //用于保存数字
        for(Character c : s.toCharArray()){
            if(c>='0' && c<='9'){ //当前字符为数字
              //数字有可能不止一位
                multi = multi*10 + (c-'0');
            } else if(c == '['){  //当前字符为左括号,入栈
              //数字入栈
                stack_multi.push(multi);
                //字符串入栈
                stack_res.push(res);
                //数字和字符串置空置零
                res = "";
                multi = 0;
            } else if(c == ']'){  //当前字符为有括号,出栈
              //将前面的字符串保存下来,用于拼接,便于完成下一次操作
                String curr = stack_res.pop();
                //数字出栈,作为循环的次数
                int count = stack_multi.pop();
                String temp = "";
                for(int i=0; i<count; i++){
                    temp += res;
                }
                res = curr + temp;
            } else {  //当前字符为字母,追加到结果后面
                res+=c;
            }
        }
        return res;
    }
}



四、时空复杂度分析



时间复杂度:        O(N)


空间复杂度:        O(N)


参考:力扣大佬的题解

里面还有递归版本,效率打败100%用户。

相关文章
|
18天前
|
存储 安全 Java
Java零基础-字符串详解
【10月更文挑战第18天】Java零基础教学篇,手把手实践教学!
95 60
|
8天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
29 6
|
1月前
|
Java 数据库
案例一:去掉数据库某列中的所有英文,利用java正则表达式去做,核心:去掉字符串中的英文
这篇文章介绍了如何使用Java正则表达式从数据库某列中去除所有英文字符。
46 15
|
24天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
31 1
|
1月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
24 9
|
1月前
|
Java
JAVA易错点详解(数据类型转换、字符串与运算符)
JAVA易错点详解(数据类型转换、字符串与运算符)
48 4
|
2月前
|
Java 数据库
java小工具util系列1:日期和字符串转换工具
java小工具util系列1:日期和字符串转换工具
50 3
|
2月前
|
SQL Java 索引
java小工具util系列2:字符串工具
java小工具util系列2:字符串工具
18 2
|
2月前
|
存储 移动开发 Java
java核心之字符串与编码
java核心之字符串与编码
21 2
|
1月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
10 0