O(n) Java solution


  • 0
    F

    A string is a valiate string iff

    1. From begin to any position, count of '(' + count of '*' >= count of ')'
    2. From end back to any position, count of ')' + count of '*' >= count of '('

    Proof:
    If 1, any ')' will always be matched by a '(' or '' on its left
    If 2, any '(' will always be matched by a ')' or '
    ' on its right
    So if 1 and 2 are satisfied, the string is valid
    Obviously if 1 or 2 are not satisfied, the string is invalid.

        int toId(char c) {
            return "()*".indexOf(c);
        }
        public boolean checkValidString(String s) {
            int sz = s.length();
            int[] fromLeft = new int[3], fromRight = new int[3];
            for (int i = 0; i < sz; ++i) {
                char c = s.charAt(i);
                int id = toId(c);
                    fromLeft[id]++;
                if (fromLeft[0]+fromLeft[2]<fromLeft[1])return false;
            }
            for (int i = sz-1;i>=0;--i){
                char c=s.charAt(i);
                int id=toId(c);
                fromRight[id]++;
                if (fromRight[1]+fromRight[2]<fromRight[0])return false;
            }
            return true;
        }
    

  • 0
    C

    very smart solution!


Log in to reply
 

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