Java solution 4ms using stack, O(N) space


  • 0
    F
    public class Solution {
        public String decodeString(String s) {
            StringBuilder res = new StringBuilder();
            Stack<int[]> si = new Stack<>();
            int i = 0;
            while(i < s.length()){
                char c = s.charAt(i);
                if(c == ']'){
                    int[] top = si.pop();
                    int endpos = res.length();
                    for(int j = 0; j < top[0] - 1; j++){
                        for(int k = top[1]; k < endpos; k++){
                            res.append(res.charAt(k));
                        }
                    }
                    i++;
                }else{
                    int count = 0;
                    while(i < s.length() && (c=s.charAt(i))>='0' && c <='9'){
                        count = 10 * count + (int)(c - '0');
                        i++;
                    }
                    if(count == 0){
                        count = 1;
                    }else{
                        i++;
                    }
                    si.push(new int[]{count, res.length()});
                    while(i < s.length() && (c=s.charAt(i)) >='a' && c <= 'z'){
                        res.append(c);
                        i++;
                    }
                }            
            }
            return res.toString();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.