Valid Parentheses String#

Given a string consisting of only three types of characters: (, ), and *, write a function to check whether this string is a valid string. Valid strings have the following rules:

• Any left parenthesis ( must have a corresponding right parenthesis ).
• Any right parenthesis ) must have a corresponding left parenthesis (.
• Left parenthesis ( must precede their corresponding right parenthesis ).
• * can be treated as a single right parenthesis ), or single left parenthesis (, or an empty string.
• An empty string is also considered a valid string.

Example#

Solution#

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    var n = s.length;
    var lSeq = 0;
    for(let i=0;i<n;++i){
        if(s[i] !== ")") ++lSeq;
        else --lSeq;
        if(lSeq < 0) return false; 
    }
    if(lSeq === 0) return true;
    var rSeq = 0;
    for(let i=n-1;i>=0;--i){
        if(s[i] !== "(") ++rSeq;
        else --rSeq;
        if(rSeq < 0) return false;
    }
    return true;
};

Idea#

We use a two-way traversal method with two extreme boundary assumptions. First, assuming all * are (, because the left parentheses must be on the left side of the paired ones. So, we iterate from left to right to see if it is enough to cover all the ). Then suppose all * are ), because the right parenthesis must be on the right side of the paired ones, we iterate from right to left to see if it is enough to cover all the (. If both can hold true, then we can meet the requirements of the problem. The specific implementation uses two counting variables lSeq and rSeq. During forward scanning, if a non-) is encountered, the counting variable is incremented, otherwise it is decremented. If the count is negative, it means it does not meet the matching condition, so we directly return false. If a complete match is found in one pass, we return true directly, and no longer perform reverse traversal. The same logic applies to reverse traversal. When a non-( is encountered during reverse scanning, the counting variable is incremented, otherwise it is decremented. If the count is negative, it means it does not meet the matching condition, so we directly return false. If both traversals are completed normally, we return true.

Daily Topic#

Reference#