括号匹配 -- 利用道具* 版本

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串

解：

1.关键：(关键是 理解 cnt_min 和 cnt_max的含义)

（1）其实 原来的那个 母题 不一定要用 stack栈实现 ， 也可以用 记录 “抵消 后的 left括号的数量”

(2)

cnt_min++;  //min记录 还需要的 )的最小数量

cnt_max++;  //max记录( 和 * 的数量之和,这就是还能承受的)最大数量

(3)然后 分 3种 情况对 这个字符串进行 讨论即可

2.代码：

class Solution {
public:
    bool checkValidString(string s) {
        //借鉴讨论区的 一个 思路： 
        //其实 原始的括号匹配题目 也可以不用stack实现， 而是用记录之前的(左括号的未抵消数量
        int cnt_min=0;
        int cnt_max=0;
        int size = s.size();
        for(int i=0;i<=size-1;i++)
        {
            if(s[i] == '(')
            {
                cnt_min++;  //min记录(的数量
                cnt_max++;  //max记录( 和 * 的数量之和
            }
            else if(s[i] == '*')
            {
                cnt_min = max(cnt_min-1,0);
                cnt_max++;
            }
            else if(s[i] == ')')
            {
                cnt_min = max(cnt_min-1,0);
                cnt_max--;
                if(cnt_max < 0)
                {
                    return false;
                }
            }
        }
        //收尾
        if(cnt_min!=0)
        {
            return false;
        }
        return true;
    }
};