394. Decode String

Question

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 105.

Example 1:

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

Example 2:

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

Algorithm

For this question, I did not come up with a solution at first until I checked with standard answer.

You push all the things to the stack except ']' because each time you saw ']', you need to pop from stack and do:

1. Pop up all the chars and store them in a list until you have a left bracket;
2. Pop the left bracket
3. Calculate the number, since the number is pop up in reverse order so the calculation should be don't in a reverse order;
4. Append string segment number times and push back the calculated string segment

Code

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack();
        
        StringBuilder sb = new StringBuilder();
        
        for (Character ch : s.toCharArray()) {
            if (ch == ']') {
                List<Character> list = new ArrayList<>();
                while (stack.peek() != '[') {
                    list.add(stack.pop());
                }
                
                stack.pop(); // pop '['
                
                int num = 0;
                int base = 1;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    num = num + (stack.pop() - '0') * base;
                    base *= 10;
                }
                while (num != 0) {
                    for (int j = list.size() - 1; j >= 0; j--) {
                        stack.push(list.get(j));
                    }
                    num--;
                }
            } else {
                stack.push(ch);
            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
        
    }
}

Thoughts

For this kind of question, with left right bracket, normally it's solved with stack.

One thing worth to care about is that do you need to push the bracket into the stack? Yes normally.

For previous question we solved 71. Simplify path, the '/' is a delineation and we could split the string and ignore the '/'.

In my view, the left and right bracket has a sequence and thus, we need to keep them.

These are one kind of stack questions, 1. Sequence has relationship; 2. Special character like '[]' who has special meaning back and forth.