678. Valid Parenthesis String -------M ~~~~~~~~~

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

• Any left parenthesis '(' must have a corresponding right parenthesis ')'.
• Any right parenthesis ')' must have a corresponding left parenthesis '('.
• Left parenthesis '(' must go before the corresponding right parenthesis ')'.
• '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

 

Constraints:

• 1 <= s.length <= 100
• s[i] is '(', ')' or '*'.

A:

        这个错了好多次。 哎~~~~~~悲伤~~~~~~~水平不够啊

看看这个，对不对？

class Solution {
public:
    bool checkValidString(string s) {
        //from left to right, count of (+possible(, which is *, always >=0
        //from left to right, count of )+possible(, which is *, always <=0
        int cL = 0, cR = 0, cS = 0;//count of Left, Right, and Star
        for(const char ch : s){
            if(ch=='('){
                ++cL;
            }else if(ch==')'){
                ++cR;
            }else{ // is *
                ++cS;
            }
            if(cR > cL + cS){
                return false;
            }
        }
        return cL > cR+cS? false : true;
    }
};

是错误的， 不能保证  *( 的情况

所以我们真正关心的，还是其 左右的balance情况，如果走一遍的话，核心是*（情况，第一个* 不能算）的。 因此需要 弄掉。

不需要stack,   只需要从左往右，  看   ‘)’   会不会太多。 

从右往左，看 '('  有没有太多

class Solution {
public:
    bool checkValidString(string s) {
        int n = s.length();
        int cLeft = 0, cRight = 0, cStar = 0;
        // check forward, make sure ')' is not too many
        for(auto ch : s){
            if(ch =='(')
                cLeft ++;
            else if(ch ==')')
                cRight++;
            else 
                cStar++;
            if(cLeft + cStar < cRight)
                return false;
        }
        // check backward, make sure '(' is not too many 
        cLeft = 0, cRight = 0, cStar = 0;
        for(int i = n-1;i>=0;i--){            
            if(s[i] =='(')
                cLeft ++;
            else if(s[i] ==')')
                cRight++;
            else 
                cStar++;
            
            if(cLeft > cStar + cRight)
                return false;
        }        
        return true;
    }
};

稍微简化了一下。把3个变量用 map 表示

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: bool checkValidString(string s) { unordered_map<char,int> M; // check forward, make sure ')' is not too many for(auto ch : s){ M[ch]++; if(M['('] + M['*'] < M[')']) return false; } M.clear(); // check backward, make sure '(' is not too many for(int i = s.length()-1;i>=0;i--){ M[s[i]]++; if(M['('] > M['*'] + M[')']) return false; } return true; } };

然而，官方答案用了DP 和greedy 2中方法。

Approach #3: Greedy [Accepted]

Intuition

When checking whether the string is valid, we only cared about the "balance": the number of extra, open left brackets as we parsed through the string. For example, when checking whether '(()())' is valid, we had a balance of 1, 2, 1, 2, 1, 0 as we parse through the string: '(' has 1 left bracket, '((' has 2, '(()' has 1, and so on. This means that after parsing the first i symbols, (which may include asterisks,) we only need to keep track of what the balance could be.

For example, if we have string '(***)', then as we parse each symbol, the set of possible values for the balance is [1] for '('; [0, 1, 2] for '(*'; [0, 1, 2, 3] for '(**'; [0, 1, 2, 3, 4] for '(***', and [0, 1, 2, 3] for '(***)'.

Furthermore, we can prove these states always form a contiguous interval. Thus, we only need to know the left and right bounds of this interval. That is, we would keep those intermediate states described above as [lo, hi] = [1, 1], [0, 2], [0, 3], [0, 4], [0, 3].

Algorithm

Let lo, hi respectively be the smallest and largest possible number of open left brackets after processing the current character in the string.

If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we must write a right bracket, so hi--. If hi < 0, then the current prefix can't be made valid no matter what our choices are. Also, we can never have less than 0 open left brackets. At the end, we should check that we can have exactly 0 open left brackets.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: bool checkValidString(string s) { // balance = [lo, hi] as the number of extra '(' than ')' int lo = 0,hi = 0; for(auto ch : s){ lo += ch=='(' ? 1:-1; hi += ch==')' ? -1:1; if(hi<0) return false; lo = max(lo,0); } return lo==0; } };

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the length of the string. We iterate through the string once.

• Space Complexity: $O(1)$, the space used by our lo and hi pointers. However, creating a new character array will take $O(N)$ space.