LeetCode 394. 字符串解码 | Python

大梦三千秋 2020/5/29 8:26:18

394. 字符串解码 题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/decode-string 题目 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可…

394. 字符串解码


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/decode-string

题目


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

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解题思路


思路:栈

在上面的例子中,第二个示例出现了括号内嵌的情况。本题中,比较难处理的也是这部分。

在本篇幅中,我们使用栈的思路,来解决本题。上面提及出现的括号内嵌的情况,当我们返回的时候,要从内部往外去生成与拼接字符,这也是我们使用栈的原因,因为栈具有先入后出的特性。

在这里,我们栈里面,每项需要存储两个信息,一个是左括号前面的字符,一个是左括号前面的数字。

例如示例 2,3[a2[c]],其中 a2[c] 这一部分,入栈时应该是这样的:('a', 2),后面会遍历字符 c,遇到右括号的时候,要进行出栈操作。弹出的元素 ('a', 2),这里要跟字符 c 拼接称新的字符串 a + 2 * 'c',也就是 acc

具体的做法:

  • 遍历元素为数字时,将数字字符转换为数字,这里用于后面字符解码倍数运算;
  • 遍历元素为字母时,这个时候,直接将字符加在结果尾部;
  • 遍历元素为左括号时,要将左括号前面的字母和数字进行入栈,入栈之后,要将存储这两项的变量重置;
  • 遍历元素为右括号时,进行出栈,拼接字符。

算法实现过程的图解如下:

图解

具体的代码实现如下。

代码实现


class Solution:
    def decodeString(self, s: str) -> str:
        # 辅助栈,每项存储两个信息,一个左括号前面的字符,一个左括号前面的数字
        stack = []
        mult = 0
        ans = ''

        for char in s:
            # 当字符为数字字符时,转换为数值,用于后续倍数运算
            if char.isdigit():
                # mult = int(char)
                # 这里要注意数字位数,
                # 上面的写法,遇到用例 "100[leetcode]" 出错了,这里改为
                mult = mult * 10 + int(char)
            # 遇到左括号时,将前面的字符和数值入栈
            elif char == '[':
                stack.append((ans, mult))
                # 这里要重置存储这两项的变量
                ans = ''
                mult = 0
            # 遇到右括号时,出栈
            elif char == ']':
                front_char, cur_mult = stack.pop()
                ans = front_char + cur_mult * ans
            # 这里表示遇到的是字符,直接添加到 ans 末尾
            else:
                ans += char

        return ans


实现结果


实现结果

总结


  • 本题中比较难处理的是括号内嵌的问题,这里要从内部往外扩展,这里符合栈先入后出的特性,所以采用栈的思路来解决此问题。
  • 构建辅助栈,每项存储两个信息,一个左括号前面的字符,一个左括号前面的数值
  • 遍历字符串,对不同的情况进行相应的处理:
    • 遍历元素为数字字符时,转换为数值,用于后续倍数计算(这里要注意数字位数,不一定只有个位数数字)
    • 遍历元素为字母时,添加到结果末尾
    • 遍历元素为左括号时,进行入栈操作,将左括号前面的字符和数字压入栈中,同时要重置存储这两项的变量
    • 遍历元素为右括号时,开始出栈,同时拼接字符。

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[LeetCode 394. 字符串解码 | Python]http://www.zyiz.net/tech/detail-137697.html

上一篇:【老板叫我了】python常用方法和运算符整理

下一篇:Python进阶量化交易专栏场外篇30-让Web和GUI鱼和熊掌兼得

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程