c++solution, easy to understand, O(n) time, O(1) space


  • 0
    H
    class Solution {
    public:
        bool checkValidString(string s) {
            int n = s.size(), nl = 0/*number of left parenthesis*/, nr = 0/*number of right parenthesis*/;
            for (int i = 0; i < n; ++i) {
                //scan from left to right
                if (s[i] == '(' || s[i] == '*') ++nl;//treat all the '*' as '('
                if (s[i] == ')') {
                    if (nl == 0) {//if no left parenthesis can pair this incoming right parenthesis, return false
                        return false;
                    } else {
                        --nl;
                    }
                }
                //scan from right to left
                if (s[n - i - 1] == ')' || s[n - i - 1] == '*') ++nr;//treat all the '*' as ')'
                if (s[n - i - 1] == '(') {
                    if (nr == 0) {//if no right parenthesis can pair this incoming left parenthesis, return false
                        return false;
                    } else {
                        --nr;
                    }
                }
            }
            return true;//when both direction were passed
        }
    };
    

Log in to reply
 

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