394. Decode String

Source

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”

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

Constraints:

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All the integers in s are in the range [1, 300].

Dry Run for a test case to better under the solution:

Certainly! Let’s go through the code with an example where the character is ’]’:

Suppose the input string is "3[a2[bc]d]ef". We’ll step through the code with this example:

1. Initialize variables and stacks:

   • intStack: empty
   • strStack: empty
   • cur: empty StringBuilder
   • k: 0

2. Loop through each character in the input string:

   • Character ‘3’ (Digit)

     k = k * 10 + ch - '0' => k = 0 * 10 + 3 - '0' => k = 3
     

     Update k to 3.

   • Character ’[’ (Open Bracket)

     intStack: [3]
     strStack: [""]
     cur: ""
     k: 0
     

     Push the current repeat count 3 onto intStack, push the current StringBuilder cur onto strStack, and reset cur and k.

   • Character ‘a’ (Regular character)

     cur: "a"
     

     Append ‘a’ to the current StringBuilder cur.

   • Character ‘2’ (Digit)

     k = k * 10 + ch - '0' => k = 0 * 10 + 2 - '0' => k = 2
     

     Update k to 2.

   • Character ’[’ (Open Bracket)

     intStack: [3, 2]
     strStack: ["", "a"]
     cur: ""
     k: 0
     

     Push the current repeat count 2 onto intStack, push the current StringBuilder cur onto strStack, and reset cur and k.

   • Character ‘b’ (Regular character)

     cur: "b"
     

     Append ‘b’ to the current StringBuilder cur.

   • Character ‘c’ (Regular character)

     cur: "bc"
     

     Append ‘c’ to the current StringBuilder cur.

   • Character ’]’ (Close Bracket)

     tmp = cur = "bc"
     cur = strStack.pop() = "a"
     k = intStack.pop() = 2
     

     Pop the repeat count (2) and the previous StringBuilder ("a") from their respective stacks. Append the current StringBuilder (tmp = "bc") to the previous StringBuilder (cur = "a") repeated k times.

     cur: "abcbc"
     

   • Character ‘d’ (Regular character)

     cur: "abcbcd"
     

     Append ‘d’ to the current StringBuilder cur.

   • Character ’]’ (Close Bracket)

     tmp = cur = "abcbcd"
     cur = strStack.pop() = ""
     k = intStack.pop() = 3
     

     Pop the repeat count (3) and the previous StringBuilder ("") from their respective stacks. Append the current StringBuilder (tmp = "abcbcd") to the previous StringBuilder (cur = "") repeated k times.

     cur: "abcbcdabcbcdabcbcd"
     

   • Character ‘e’ (Regular character)

     cur: "abcbcdabcbcdabcbcde"
     

     Append ‘e’ to the current StringBuilder cur.

   • Character ‘f’ (Regular character)

     cur: "abcbcdabcbcdabcbcdef"
     

3. Return the final result:

   "abcbcdabcbcdabcbcdef"
   

So, the given example demonstrates how the code processes the input string when encountering the character ’]‘. It repeatedly pops the repeat count and the previous StringBuilder from their respective stacks, appends the current StringBuilder to the previous one repeated k times, and continues building the final decoded string.

Solution:

class Solution {
    public String decodeString(String s) {
        Deque<Integer> countStack = new ArrayDeque<>();
        Deque<StringBuilder> strStack = new ArrayDeque<>();
 
        StringBuilder cur = new StringBuilder();
        int k = 0;
 
        for(char ch: s.toCharArray()){
            if(Character.isDigit(ch)){
                k = k * 10 + ch - '0';
            } else if(ch == '['){
                countStack.push(k);
                strStack.push(cur);
                cur = new StringBuilder();
                k = 0;
            } else if(ch == ']'){
                StringBuilder temp = cur;
                cur = strStack.pop();
                for(k = countStack.pop(); k > 0; k--){
                    cur.append(temp);
                }
            } else{
                cur.append(ch);
            }
        }
 
        return cur.toString();
    }
}