基本信息

  • 题号：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 原理，但是要一次性做出，不大容易啊😭
  • 解码编码问题貌似属于亚麻常考类😭