Very concise C++ solution with explaination. No DP


  • 4
    W

    Since * can be used as 3 kinds of char, if we do backtrack the complexity can blow up if the string is *****.... We need to find a non-trivial method.
    Without *, we can just use a number to indicate the unmatch (, ( will increment it and ) will decrement it. We don't want this number less than 0 all the time and it should be 0 when all the string has been matched.
    When * is introduced, the number becomes a range, indicating the number of possible unmatched ( found. One * just expand the range by 1. And we can use the same principle to check if the criteria above is within the range.

    class Solution {
    public:
        bool checkValidString(string s) {
            int lower = 0, upper = 0;
            for (char c : s) {
                if (c=='(') {
                    lower++;
                    upper++;
                } else if (c==')') {
                    lower--;               
                    upper--;
                } else { // * encountered
                    lower--;
                    upper++;
                }
                lower = max(lower, 0);
                if (upper<0) // unmatched ')' found in the middle of string
                    return false;
            }
            return lower==0;
        }
    };
    
    

Log in to reply
 

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