394. Decode String

[songyy5517]

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]. The test cases are generated so that the length of the output will never exceed $10^5$.

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"

Intuition This problem is to decode specific strings containing square brackets. From the description, we notice that the square brackets can be nested. Therefore, we can use stacks to simulate the decoding process. Specifically, we can define two stacks to store the repetition time and the previous decoded string of the current brackets. Then loop through the string, for each character, if it is a letter, then we add it to the current decoded string res; if it is a number, then we update the value of the repetition time; if it is the left bracket, we put the current repetition time and decoded string into stacks; if it is the right bracket, we decode the string of the current brackets according to its corresponding repetition time in the stack, and then concatenate it with the previous decoded string in the stack to form the final decoded string.

[songyy5517]

Approach: Stack

1. Exception handling;
2. Define variables:
   • stack_str: stores the previous decoded strings before the current brackets;
   • stack_num: stores the repetition time of the previous brackets;
   • res: the current decoded string;
3. Loop through the string, for each character: （1）If it is a number, then update the value of the repetition time; （2）If it is a letter, then add it to the current decoded string res; （3）If it is the left bracket, put the current repetition time and decoded string into stacks; （4）If it is the right bracket, decode the string of the current brackets according to its corresponding repetition time in the stack, and then concatenate it with the previous decoded string in the stack to form the final decoded string.
4. Return the final result res.

Complexity Analysis

• Time complexity: $O(N)$, looping through the whole string costs $O(N)$ . All the integers in the string are in [1, 300], so decoding and concatenating the strings in each pair of brackets takes $O(1)$ time ;
• Space complexity: $O(N)$ , additionally define two stacks, which takes up the space of $O(N)$ in the worst case, where there are $N$ pairs of brackets.

[songyy5517]

class Solution {
    public String decodeString(String s) {
        // Intuition: String & Stack.
        // 1. Exception handling
        if (s == null || s.length() == 0)
            return "";

        // 2. Define variables
        Stack<String> stack_str = new Stack();    // record the preceding string of the current []
        Stack<Integer> stack_num = new Stack();    // record the repeating time of the current []
        StringBuffer res = new StringBuffer();
        int repeat = 0;

        // 3. Iterate over the string
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);

            // 1. letter
            if (c >= 'a' && c <= 'z')
                res.append(c);
            // 2. number
            else if (c >= '0' && c <= '9')
                repeat = repeat * 10 + c - '0';
            // 3. [: Store the string and repeating number before this [ into Stack
            else if (c == '['){
                stack_str.push(res.toString());
                stack_num.push(repeat);
                res = new StringBuffer();
                repeat = 0;
            }

            // 4. Obtain the decoded string before this ] and store it to res
            else if (c == ']'){
                // Obatin the previous string and repeating number of this []
                StringBuffer substr = new StringBuffer(stack_str.pop());
                int num = stack_num.pop();

                // substr + num * res
                for (int j = 0; j < num; j++)
                    substr.append(res); 
                res = substr;
            }
        }

        return res.toString();
    }
}

[songyy5517]

2024/5/23