C++ simple O(n) time O(1) space solution, no Backtracking or DFS


  • 0
    M
        bool checkValidString(string s) {
            int star=0, l=0, r=0;
            for(int i=0;i<s.size();i++) {
                if(s[i]=='*') star++;
                else if(s[i]=='(') l++;
                else l--;
                if(l+star<0) return false;
            }
            star=0;
            for(int i=s.size()-1;i>=0;i--) {
                if(s[i]=='*') star++;
                else if(s[i]==')') r++;
                else r--;
                if(r+star<0) return false;
            }
            return true;
        }

Log in to reply
 

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