MockInterview:394. Decode String

Medium

Given an encoded string, return it's 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; 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 won't be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

My code:

class Solution {
    public String decodeString(String s) {
        if(s == null) return null;
        if(s.length() == 0) return s;
        int n = s.length();
        return decodeString(s,0,n-1);
    }
    
    public String decodeString(String s, int start, int end){
        if(end < start) return "";
        if(s.substring(start,end+1).indexOf("[") == -1) return s.substring(start,end+1);
        StringBuilder sb = new StringBuilder();
        for(int i = start; i <= end;){
            char c = s.charAt(i);
            int num = 0;
            while(Character.isDigit(c)){
                int digit = c - '0';
                num = num * 10 + digit;
                i++;
                c = s.charAt(i);
            }
            System.out.println("num:"+num);
            if(c == '['){
                int endBIndex = findMatchIndex( s, i, end);
                System.out.println(endBIndex);
                //String substring = s.substring(start + 1,endBIndex -1);
                String subRes = decodeString(s, i+1, endBIndex - 1);
                for(int j = 1; j <= num; j++){
                    sb.append(subRes);
                }
                i = endBIndex + 1;
            }else{
                sb.append(c);
                i++;
            }
        }
        return sb.toString();
    }
    
    public int findMatchIndex(String s, int start, int end){
        int open = 1;
        int close = 0;
        int i = start + 1;
        for(; i <= end; i++){
            char c = s.charAt(i);
            if(c == '['){
                open++;
            }else if(c == ']'){
                close++;
            }
            if(open == close){
                break;
            }
        }
        return i;
    }
}

Solution: use two stacks, one for integer count, the other for  the left part string of [ in the same bracket level. take 1[a2[b]] for example, for the second bracket, left part string is 'a'. from the beginning of the outer bracket until the counter.
1) for each bracket level, there is a block to combine the character. take a2[b]c, when encounter a '[', assign a empty for block, to restart a block string for inner bracket. when encounter ']', assign the stack peek to block, to revert block variable to the outer bracket string.
2) for [, push countStack and leftStack. and restart a new count number and empty block string for inner bracket.
3) for ], in this bracket level, combine the string from the begin to ](left part + count * inner bracket).
take a2[b]c for example, when we see ], the block will assgin a first, then append bb until ].
4) for the left part of [ and the right part of ], just append the character to block.

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<Integer>();
        Stack<String> leftStack = new Stack<String>();
        int number = 0;
        String block = "";
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            System.out.println(c);
            if(Character.isDigit(c)){
                while(Character.isDigit(c)){
                    number = number * 10 + c - '0';
                    i++;
                    if(i >= s.length()) break;
                    c = s.charAt(i);
                }
                i--;
            }else if(c == '['){
                leftStack.push(block);
                countStack.push(number);
                number = 0;
                block = "";
            }else if( c == ']'){
                String leftpart = leftStack.pop();
                StringBuilder sb = new StringBuilder(leftpart);
                int count = countStack.pop();
                while(count > 0){
                    sb.append(block);
                    count--;
                }
                block = sb.toString();
            }else{
                block = block + c;
            }
        }
        return block;
    }
}