Java - stack - not fast - but ez to understand


  • 1
    C

    beats 50%, slow but ez to understand

    public String decodeString(String s) {
            if (s == null || s.length() == 0) {
                return s;
            }
            
            Stack<String> stack = new Stack<>();
         
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch != ']') { // push all except ']'
                    stack.push(String.valueOf(ch));
                } else {
                    // concatenate string
                    StringBuilder sb1 = new StringBuilder();
                    while (!stack.peek().equals("[")) {
                        sb1.insert(0, stack.pop());
                    }
                    // pop "["
                    stack.pop();
                    // generate counter
                    StringBuilder sb2 = new StringBuilder();
                    while (!stack.empty() && stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <= '9') {
                        sb2.insert(0, stack.pop());
                    }
                    int counter = Integer.parseInt(sb2.toString());
                    // generate new string
                    StringBuilder sb3 = new StringBuilder();
                    for (int j = 0; j < counter; j++) {
                        sb3.append(sb1.toString());
                    }
                    // push new string back
                    stack.push(sb3.toString());
                }
            }
            
            // final concat
            StringBuilder ans = new StringBuilder();
            while (!stack.empty()) {
                ans.insert(0, stack.pop());
            }
            
            return ans.toString();
        }
    

Log in to reply
 

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