Java O(n) time, O(1) Space, Easy to understand


  • 0

    The idea is to have two variable, left and star to record the number of left brackets and * in the string. First validate '(' then ')'. This method needs to parse the string twice but it is still O(n) time complexity.

    class Solution {
        public boolean checkValidString(String s) {
            if (s == null || s.length() == 0) return true;
            int left = 0, star = 0;
            char[] chs = s.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                if (chs[i] == '(') {
                    left++;
                } else if (chs[i] == ')') {
                    if (left == 0 ) {
                        if (star == 0) return false;
                        star--;
                    } else {
                        left--;
                    }
                } else if (chs[i] == '*') {
                    star++;
                }
            }
            left = star = 0;
            for (int i = chs.length - 1; i >= 0; i--) {
                if (chs[i] == ')') {
                    left++;
                } else if (chs[i] == '(') {
                    if (left == 0 ) {
                        if (star == 0) return false;
                        star--;
                    } else {
                        left--;
                    }
                } else if (chs[i] == '*') {
                    star++;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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