字符串解码(力扣 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%用户。

相关文章
|
3月前
|
存储 算法 Java
惊!Java程序员必看:JVM调优揭秘,堆溢出、栈溢出如何巧妙化解?
【8月更文挑战第29天】在Java领域,JVM是代码运行的基础,但需适当调优以发挥最佳性能。本文探讨了JVM中常见的堆溢出和栈溢出问题及其解决方法。堆溢出发生在堆空间不足时,可通过增加堆空间、优化代码及释放对象解决;栈溢出则因递归调用过深或线程过多引起,调整栈大小、优化算法和使用线程池可有效应对。通过合理配置和调优JVM,可确保Java应用稳定高效运行。
135 4
|
12天前
|
存储 算法 Java
🧠Java零基础 - Java栈(Stack)详解
【10月更文挑战第17天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
12 2
|
29天前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
28 2
|
28天前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
9 0
|
29天前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
16 0
|
29天前
|
算法 Java
LeetCode(一)Java
LeetCode(一)Java
|
3月前
|
Java 索引
java中的栈(利用数组实现栈)
这篇文章通过Java代码示例介绍了如何使用数组实现栈操作,包括栈的初始化、入栈、出栈、判断栈满和空以及遍历栈的方法。
java中的栈(利用数组实现栈)
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6
|
3月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
66 2
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
48 1