394. Decode String Medium

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; there are 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 will not be input like 3a or 2[4].

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

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

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

Example 4:
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Approach

Input: An encoded string s

Output: Return the decoded string

This problem belongs to the Expression Evaluation Stack category.

We observe that as long as a ] appears, there must be a form of number + [letters before it.

So we can use a stack to store previously encountered characters.

When we encounter a ], we trace back in the stack to find the letters inside the brackets and the number outside the brackets.

After organizing, we can obtain the decrypted partial string and save it back into the stack.

Finally, we concatenate all the values in the stack together to get the fully decrypted string.

Implementation

python

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

        for char in s:
            if char != ']':
                # If it's not a right bracket, push it straight onto the stack (including letters, numbers, and left brackets)
                stack.append(char)
            else:
                # Met a right bracket, begin decoding logic

                # 1. Pop out the string inside the square brackets
                decoded_str = ''
                while stack and stack[-1] != '[':
                    decoded_str = stack.pop() + decoded_str  # Prepend because of stack LIFO
                stack.pop()  # Pop the '['

                # 2. Extract the number in front of the string (can be multi-digit)
                k = ''
                while stack and stack[-1].isdigit():
                    k = stack.pop() + k  # Prepend order

                # 3. Push the duplicated expanded string back into the stack
                stack.append(int(k) * decoded_str)

        # Finally, join all string snippets in the stack to return the complete string
        return ''.join(stack)

javascript

/**
 * @param {string} s
 * @return {string}
 */
const decodeString = function(s) {
    const stack = [];

    for (c of s) {
        if (c !== ']') {
            stack.push(c);
        } else {
            let curr_str = '';
            while (stack.length && stack.at(-1) !== '[') {
                curr_str = stack.pop() + curr_str;
            }
            stack.pop();

            let curr_num = '';
            while (stack.length && /[0-9]/.test(stack.at(-1))) {
                curr_num = stack.pop() + curr_num;
            }

            stack.push(curr_str.repeat(parseInt(curr_num)));
        }
    }

    return stack.join('');
};

Complexity Analysis

• Time Complexity: O(n) (ignoring the length of the string to be generated)
• Space Complexity: O(n)

Links

394. Decode String (English)

394. 字符串解码 (Chinese)