写点什么

【LeetCode】字符串解码 Java 题解

作者:Albert
  • 2022 年 10 月 08 日
    北京
  • 本文字数:1264 字

    阅读完需:约 4 分钟

题目描述

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


编码规则为: 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"
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/decode-string著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是字符串题目,题目规定了一种算法,编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。看到了[], [] 处理问题,我们一般使用栈来处理,栈是一种后进先出的数据结构。

  • 具体到这个题目,我们可以分情况讨论,没有[]的字符部分,无需重复。有[]的部分需要重复,需要我们分别处理数字字符和[]的内容。定义 digitStack, resStack 两个栈,用来存储数字和中间结果。当遇到[时候,将数字入 digitStack,同时结果插入 resStack。当遇到]时候,将[]中间的数据重复 currentDigit 次, currentDigit 是 digitStack 中取出的。然后将之前 resStack 的数据取出,拼接一起,在放入 resStack 中。字符串中处理频繁修改的时候,可以使用 StringBuilder 提升执行效率。

  • 具体实现代码如下,供参考。

通过代码

class Solution {    public String decodeString(String s) {        StringBuilder result = new StringBuilder();        int digit = 0;        LinkedList<Integer> digitStack = new LinkedList<>();        LinkedList<String> resStack = new LinkedList<>();
for (Character c : s.toCharArray()) { if (c == '[') { digitStack.addLast(digit); resStack.addLast(result.toString()); digit = 0; result = new StringBuilder(); } else if (c == ']') { StringBuilder tmp = new StringBuilder(); int currentDigit = digitStack.removeLast(); for (int i = 0; i < currentDigit; i++) { tmp.append(result); } result = new StringBuilder(resStack.removeLast() + tmp); } else if (c >= '0' && c <= '9') { digit = digit * 10 + Integer.parseInt(c + ""); } else { result.append(c); } }
return result.toString(); }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 3
用户头像

Albert

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】字符串解码Java题解_LeetCode_Albert_InfoQ写作社区