企业官网建设流程全解析

给你一个只包含三种字符的字符串，支持的字符类型分别是'('、')'和'*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回true。

有效字符串符合如下规则：

• 任何左括号'('必须有相应的右括号')'。
• 任何右括号')'必须有相应的左括号'('。
• 左括号'('必须在对应的右括号之前')'。
• '*'可以被视为单个右括号')'，或单个左括号'('，或一个空字符串""。

示例 1：

输入：s = "()"输出：true

示例 2：

输入：s = "(*)"输出：true

示例 3：

输入：s = "(*))"输出：true

提示：

• 1 <= s.length <= 100
• s[i]为'('、')'或'*'

分析：由于星号*可以被看成左括号(、右括号)或空字符串，因此判断字符串是否合法时，需要同时考虑括号的数量关系以及星号出现的位置。可以通过两次贪心遍历分别处理这两个方向的问题。

从左到右遍历字符串。在遍历过程中，分别记录左括号数量l、右括号数量r和星号数量cnt。对于任意一个前缀，如果右括号的数量大于左括号和星号数量之和，即 r > l + cnt，则说明即使把当前前缀中的所有星号都看成左括号，也无法匹配已经出现的右括号。由于后面的字符无法与前面已经出现的右括号匹配，因此此时字符串一定无效，可以直接返回false。

但是，仅进行从左到右的遍历还不够。例如字符串：*(，从左到右统计时，左括号数量没有超过“右括号数量 + 星号数量”，但实际上星号出现在左括号之前，不能将其看成右括号来匹配后面的左括号。

因此还需要从右到左再次遍历字符串。同样记录左括号数量l、右括号数量r和星号数量cnt。对于任意一个后缀，如果左括号的数量大于右括号和星号数量之和，即 l > r + cnt，则说明即使把当前后缀中的所有星号都看成右括号，也无法匹配已经出现的左括号，因此字符串一定无效，返回false。

如果从左到右和从右到左的两次遍历都没有出现无法匹配的情况，则说明所有多余的左括号和右括号都可以通过适当地将星号看成左括号、右括号或空字符串进行匹配，因此字符串是有效的括号字符串。

class Solution { public: bool checkValidString(string s) { int l=0,r=0,cnt=0,n=s.length(); for(int i=0;i<n;++i) { if(s[i]=='(')l++; else if(s[i]==')')r++; else cnt++; if(r>l+cnt)return false; } l=r=cnt=0; for(int i=n-1;i>=0;--i) { if(s[i]=='(')l++; else if(s[i]==')')r++; else cnt++; if(l>r+cnt)return false; } return true; } };