Problem description:

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

1
2
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Solution:

Stack:
Thought process is to divide the case into digit, character, [, ].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def decodeString(self, s: str) -> str:
        # stack
        # 4 cases in the string
        # digit, character, '[', ']'
        stack, cur_string, cur_num = [], "", 0
        for c in s:
            if c.isdigit():
                cur_num = cur_num*10 + int(c)
            elif c == '[':
                # means we have cur_num and cur_string exist 
                # put them into stack 
                stack.append(cur_string)
                stack.append(cur_num)
                cur_string, cur_num = "", 0
            elif c == ']':
                repeat = stack.pop()
                prev_string = stack.pop()
                cur_string = prev_string + repeat*cur_string
            else: 
                cur_string += c
        return cur_string

time complexity: $O(n)$
space complexity: $O(n)$

Solution DFS:

  1. The dfs should return a string
  2. Since the format is always valid, we expect the brackets always comes after numbers
  3. if s[i] is not number, then just append character to current level result
  4. if s[i] is number, calculate the number first. Then get the string inside bracket.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def decodeString(self, s: str) -> str:
        self.i = 0
        def dfs(s, i):
            res = ""
            while self.i < len(s) and s[self.i] is not ']':
                if not s[self.i].isdigit():
                    res += s[self.i]
                    self.i += 1
                else:
                    # is digit, so find out number of repeat first
                    n = 0
                    while i < len(s) and s[self.i].isdigit():
                        n = n*10 + int(s[self.i])
                        self.i += 1
                    
                    # the format is always valid
                    # ie: brackets would always come after numbers
                    self.i += 1 # '['
                    tmp = dfs(s, self.i)
                    self.i += 1 # ']'
                    
                    while n:
                        res += tmp
                        n -= 1
            return res

        return dfs(s, self.i)

reference:
related problem: