unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 394: Decode String

link

Our problem is a concatenation of the below pattern:

Since there are nested sub-problems, we use stack to solve it. As we process the string from left-to-right, we have two decision points:

  1. Opening bracket: When we see an opening bracket, we save prefix and num.
  2. Closing bracket: When we see a closing bracket, we repeat top of stack num times and save the result in the stack.

In the end, the stack has the repeated string.

Time: \mathcal{O}(\texttt{output-size}), space: same.

class Solution:
    def decodeString(self, s: str) -> str:
        num = 0
        prefix = []
        stack = []
        for c in s:
            if c.isdigit():
                num = 10*num + int(c)
                continue
            if c not in "[]":
                prefix.append(c)
                continue
            
            if c == "[":
                if prefix:
                    # flush prefix
                    stack.append( "".join(prefix) )
                stack.append(num)
            else:
                # flush prefix with no [...], aka suffix
                stack.append( "".join(prefix) )

                # top = [...subsol...], num
                subsol = deque()
                while not isinstance((top := stack.pop()), int):
                    subsol.appendleft(top)
                stack.append( "".join(subsol * top) )

            # Reset to solve next nested or rightwards subproblem
            num, prefix = 0, []

        # String did not end with closing bracket
        return "".join( stack+prefix )

tanvirdotzaman

,

Leave a comment