[LeetCode] 394. Decode String

 Problem : https://leetcode.com/problems/decode-string/

Use 2 stacks to decode. One stack save the counter. Another stack save of the decoded string of current level.

Time Complexity = O ( N * K ),  N = length of the input string. K = maximum value of the counter .

class Solution {
    public String decodeString(String s) {
        // save the decoded string
        // use StringBuilder to avoid repeatedly creating string object
        Stack<StringBuilder> strStack = new Stack();
        // save the counter of decoded string
        Stack<Integer> counterStack = new Stack();
        
        strStack.push(new StringBuilder());
        int count = 0;
        
        for (Character a: s.toCharArray()) {            
            if (Character.isDigit(a)) {
                // important!  counter k may have more than one digits!
                count = count * 10 + (a - '0');
            } else if (a == '[') {
                // push the counter
                counterStack.push(count);
                // push a new string builder to start a new level
                strStack.push(new StringBuilder());
                // reset the counter
                count = 0;
            } else if (a == ']') {
                // current level decoded string
                String decoded = strStack.pop().toString(); 
                // count of current level decoded string
                int n = counterStack.pop();
                
                // append the decoded string to its upper level string
                for (int j = 0; j < n; j++) {
                    strStack.peek().append(decoded);
                }
            } else {
                // append the character to current level string
                strStack.peek().append(String.valueOf(a));
            }
        }
        
        return strStack.peek().toString();
    }
}