394. Decode String

class Solution {
    public String decodeString(String s) {
        int k = 0;
        StringBuilder sb = new StringBuilder();
        Stack<String> stack = new Stack<>();
        Stack<Integer> vals = new Stack<>();
        for(char ch : s.toCharArray())
        {
            if('0' <= ch && ch <= '9') k = k * 10 + ch - '0';
            else if(ch == '[')
            {
                stack.push(sb.toString());
                sb = new StringBuilder();
                vals.push(k);
                k = 0;
            }
            else if(ch == ']')
            {
                // there is another number in front of[, and currently k = 0
                String str = sb.toString(); // current string
                int count = vals.pop();
                sb = new StringBuilder(stack.pop());
                while(count-- > 0) sb.append(str);
            }
            else sb.append(ch);
        }
        return sb.toString();
    }
    public String decodeString1(String s) {
        if(s.equals("")) return s;
        int k = 0, n = s.length();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++)
        {
            char ch = s.charAt(i);
            if(ch == '[')
            {
                int bracket = 1, j = i;
                while(bracket > 0)
                {
                    j++;
                    if(s.charAt(j) == '[') bracket++;
                    if(s.charAt(j) == ']') bracket--;
                }
                // now i points to ]
                String dec = decodeString(s.substring(i + 1, j));
                while(k-- > 0) sb.append(dec);
                sb.append(decodeString(s.substring(j + 1)));
                break;
            }
            if('0' <= ch && ch <= '9') k = k * 10 + ch - '0';
            else sb.append(ch);
        }
        return sb.toString();
    }
}