Leetcode 394. Decode String

Problem

Leetcode 394 - Decode String

Example:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Approach

We can use stack to solve this problem while iterating through the string, there can be 4 options, $curr_string$ defines current string, and $k$ defines how many times we must multiply the string in brackets

• if ch == ‘[’
  • Since we’re now starting with ‘[’, we must append whatever we had (curr_string, k) into stack
  • initialize curr_string, k again to 0
• if ch == ‘]’
  • Since we’ve ended the bracket, we must update the curr_string by popping whatever we had in last_string, and adding multiplied value for curr_string
• if ch is digit (a number)
  • We must update the value k, since k could have multiple digits, we must update using $k = k * 10 +$ int(ch)
• if ch is alpha (a character)
  • We just update the curr_string

Visualization of the Approach:

s = 3[a]2[bc]

stack = []
curr_string = ''
k = 0

Since ch is digit, update k
stack = []
curr_string = ''
k = k * 10 + int(ch) = 0 + 3 = 3

Since ch is opening bracket, put curr_string, and k into stack
stack = [('', 3)]
curr_string = ''
k = 0

Since ch is alpha, update curr_string
stack = [('', 3)]
curr_string = 'a'
k = 0

Since ch is closing bracket, update curr_string by popping stack
stack = []
curr_string = last_string + last_k * curr_string = '' + 3 * 'a' = 'aaa'
k = 0

Since ch is digit, update k
stack = []
curr_string = 'aaa'
k = k * 10 + int(ch) = 0 + 2 = 2

Since ch is opening bracket, put curr_string, and k into stack
stack = [('aaa', 2)]
curr_string = ''
k = 0

Since ch is alpha, update curr_string
stack = [('aaa', 2)]
curr_string = 'b'
k = 0

Since ch is alpha, update curr_string
stack = [('aaa', 2)]
curr_string = 'bc'
k = 0

Since ch is closing bracket, update curr_string, and pop stack
stack = []
curr_string = last_string + last_k * curr_string = 'aaa' + 2 * 'bc' = 'aaabcbc'
k = 0

return curr_string = 'aaabcbc'

Here is the Python code for the solution:

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        curr_string = ''
        k = 0

        for ch in s:
            # if ch is opening bracket, then we add the curr_string and k to stack and initialize them
            if ch == '[':
                stack.append((curr_string, k))
                curr_string = ''
                k = 0
            # if ch is closing bracket, then we pop from stack and add the multiplied string into stack
            elif ch == ']':
                last_string, last_k = stack.pop()
                curr_string = last_string + last_k * curr_string
            # if ch is digit, then update k
            elif ch.isdigit():
                k = k * 10 + int(ch)
            # if ch is character, then update curr_string
            else:
                curr_string += char
        return curr_string

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$