Beyond awesome | 越而胜己

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 ].

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