Beyond awesome | 越而胜己

Link to problem:

This problem looks simple enough, but is not easy to get right. Because we allow nesting, it’s quite obvious that we want to use stacks for the problem. The key is when to push to and pop from the stacks.

For each character, it can be in one of the four cases: digit, [, ], or other characters.

When we read a digit, we are accumulating k, so it doesn’t make sense to push k to the stack. If we pushed m to the stack every time we read a digit, we will push multiple times when we read multi-digit numbers, so it doesn’t make sense to push m either.

Similarly, when we read an “other character”, we are accumulating m, so we can’t push m to stack. We also can’t push k because we don’t want to push k repeatedly.

So we can only push on reading [, and we pop k and m on reading ].


我们读到的字符分为四种情况:数字、[] 和其他情况。

当我们读到数字时,我们需要累计当前读到的 k,显然不能将 k 入栈。此时如果将当前累计的 m 入栈,则如果遇到多位的数字就会将 m 重复入栈,所以此时也不能将 m 入栈。

当我们读到其他字符时,需要累积当前读到的 m,显然不能将 m 入栈。此时如果将当前累计的 k 入栈,也会重复入栈 k,所以也不可行。

所以当我们读到 [ 时,我们可以入栈;而当读到 ] 时,将栈上的 km 取出,并把刚刚读完的一组 k[...] 展开的结果附加到 m 后面。

class Solution:
    def decodeString(self, s: str) -> str:
        k_stack = []
        m_stack = []
        k = 0
        m = ''
        for ch in s:
            print(ch + ':')
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                m = ''
                k = 0
            elif ch == ']':
                k = k_stack.pop()
                m = m_stack.pop() + m * k
                k = 0
                m += ch
            print(k, m)
        return m
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.