LeetCode刷题实战394：字符串解码-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 字符串解码，我们先来看题面：

https://leetcode-cn.com/problems/decode-string/

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[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"

示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

解题

https://blog.csdn.net/qq_30057549/article/details/103916466

这题因为括号的嵌套，很容易想到用递归或者栈，但是实际写起来是比较复杂的，不好想出，需要多加思考。关键在于，如何保存前面已经生成（栈中没有左括号）的字符串的信息。另外，最后有个小技巧，mul*10的使用，巧妙的按字符读取n位整数。

class Solution:
    def decodeString(self, s: str) -> str:
        #思路：这种类型的题，一种思路是栈，一种思路是递归。
        #本解法用的是栈，当遇到[时，我们将数字压入栈中，并开始用cur_str记录中括号里的字母，如遇到]，就将之前的数字出栈并与当前的cur_str相乘。
        mul, cur_str = 0, ''
        stack = []
        for c in s:
            if c == '[':
                stack.append((mul, cur_str))
                mul, cur_str = 0, ''
            elif c == ']':
                n, pre = stack.pop()
                cur_str = pre + n * cur_str
            elif '0' <= c <= '9':
                mul = 10 * mul + int(c)
            else: #字母
                cur_str += c
        return cur_str