「亚麻」少说废话多做题 394 ～ 解码字符串

基本信息

• 题号：394
• 题厂：亚麻
• 难度系数：中

已知一个编码后的字符串，解码还原字符串

例如 s = "3[a]2[bc]"
返回 "aaabcbc"：a 循环 3 次，bc 循环 2 次……

解题思路

• 本题难点在于可以是双重编码

例如s = "3[a2[c]]"，返回 "accaccacc"。双 c 是在 a 的大循环内部执行的……

• 看到括号问题，于是 stack 之类的需要登场了……

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []

        # 为了解决双重括号问题，我们把所有符号扔进 stack 直到遇到反括号“]“
        # 根据题目已知字符串 pattern，括号内的一定是需要循环返回的字符串，所以遇到反括号“]“后，我们从 stack pop，并加进 substr
        # 当“[“出现后，我们需要知道当前 substr 需要循环几次，python 中调用 isdigit 即可
        for i in range(len(s)):
            if s[i] != "]":
                stack.append(s[i])
            else:
                substr = ""
                while stack[-1] != "[":
                    substr = stack.pop() + substr
                
                # pop the '['
                stack.pop()

                k = ""
                while stack and stack[-1].isdigit():
                    k = stack.pop() + k
                stack.append(int(k) * substr)

        # 整理好后在 join 返回，当然也可以创建 res 变量返回。。。
        return "".join(stack)

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All the integers in s are in the range [1, 300].

考试前一定要和考官充分讨论可能遇到的 pattern 格式

测试

• 出现多重括号时……
• ……

总结

• 这题虽然是 stack 原理，但是要一次性做出，不大容易啊😭
• 解码编码问题貌似属于亚麻常考类😭