Java, O(n), 2pass, ez to understand


  • 2
    J
    class Solution {
        public boolean checkValidString(String s) {
            int left = 0, right = 0, leftx = 0, rightx = 0;
            for (int i=0; i<s.length(); i++){
                if (s.charAt(i) == '(') left++;
                else if (s.charAt(i) == ')') left--;
                else leftx++;            
                if (left < 0){
                    if (leftx == 0) return false;
                    else{
                        leftx--;
                        left++;
                    }
                }
            }
            for (int i=s.length()-1; i>=0; i--){
                if (s.charAt(i) == '(') right--;
                else if (s.charAt(i) == ')') right++;
                else rightx++;
                if (right < 0){
                    if (rightx == 0) return false;
                    else{
                        rightx--;
                        right++;
                    }
                }
            }
            return true;
        }
    }
    

    This might be easier to understand than the top O(n) solution :)


Log in to reply
 

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