石林彝族网站建设/济南网络营销外包

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

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;}
};