越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/decode-string/

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_stack.append(m)
                k_stack.append(k)
                m = ''
                k = 0
            elif ch == ']':
                k = k_stack.pop()
                m = m_stack.pop() + m * k
                k = 0
            else:
                m += ch
            print(k, m)
        return m