Java 2 stack, keep index of each element


  • 0
     public boolean checkValidString(String s) {
    
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack3 = new Stack<>();
    
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '(') {
                    stack1.push(i);
                } else if(s.charAt(i) == '*') {
                    stack3.push(i);
                } else if(s.charAt(i) == ')') {
                    if(stack1.isEmpty() && stack3.isEmpty()) return false;
                    else if(!stack1.isEmpty()) {
                        stack1.pop();
                    } else if( !stack3.isEmpty()) {
                        stack3.pop();
                    }
                }
            }
    
            if(stack1.isEmpty()) return true;
            else {
                if(stack1.size() > stack3.size()) return false;
                else {
                    while(!stack1.isEmpty()) {
                        if(stack1.peek() < stack3.pop()) {
                            stack1.pop();
                        }
    
                        if(stack3.isEmpty() && !stack1.isEmpty()) return false;
                    }
                }
            }
            return true;
        }
    

  • 0
    F

    @Kamishirasawa-Keine I am using two stacks as well, but the original implementation is using one stack as main space and the other as temp space. The main stack stores characters instead of indices, making the worst case to be O(N2). Please find it below:

        public boolean checkValidString(String s) {
            if(s == null) return false;
            Stack<Character> s1 = new Stack<>();
            Stack<Character> s2 = new Stack<>();
            
            for(int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if(ch == '(' || ch == '*') s1.push(ch);
                else {
                    while(!s1.isEmpty() && s1.peek() != '('){
                        s2.push(s1.pop());
                    }
                    if(!s1.isEmpty()) s1.pop();
                    else {
                        if(s2.isEmpty()) return false;
                        else s2.pop();
                    }
                    while(!s2.isEmpty()) s1.push(s2.pop());
                }
            }
            
            int num = 0;
            while(!s1.isEmpty()) {
                char ch = s1.pop();
                if(ch == '*') num++;
                else num--;
                if(num < 0) return false;
            }
            return true;
        }
    

    Your solution yields O(N) run time complexity along with an O(N) space. Slightly improving the readability, the chunk after for loop could be simplified as below:

            while(!s1.isEmpty() && !s2.isEmpty()) {
                if(s1.peek() < s2.peek()){
                    s1.pop();
                    s2.pop();
                } else return false;
            }
            return s1.isEmpty();
    

Log in to reply
 

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