给你一个只包含三种字符的字符串支持的字符类型分别是(、)和*。请你检验这个字符串是否为有效字符串如果是有效字符串返回true。有效字符串符合如下规则任何左括号(必须有相应的右括号)。任何右括号)必须有相应的左括号(。左括号(必须在对应的右括号之前)。*可以被视为单个右括号)或单个左括号(或一个空字符串。示例 1输入s ()输出true示例 2输入s (*)输出true示例 3输入s (*))输出true提示1 s.length 100s[i]为(、)或*分析由于星号*可以被看成左括号(、右括号)或空字符串因此判断字符串是否合法时需要同时考虑括号的数量关系以及星号出现的位置。可以通过两次贪心遍历分别处理这两个方向的问题。从左到右遍历字符串。在遍历过程中分别记录左括号数量l、右括号数量r和星号数量cnt。对于任意一个前缀如果右括号的数量大于左括号和星号数量之和即 r l cnt则说明即使把当前前缀中的所有星号都看成左括号也无法匹配已经出现的右括号。由于后面的字符无法与前面已经出现的右括号匹配因此此时字符串一定无效可以直接返回false。但是仅进行从左到右的遍历还不够。例如字符串*(从左到右统计时左括号数量没有超过“右括号数量 星号数量”但实际上星号出现在左括号之前不能将其看成右括号来匹配后面的左括号。因此还需要从右到左再次遍历字符串。同样记录左括号数量l、右括号数量r和星号数量cnt。对于任意一个后缀如果左括号的数量大于右括号和星号数量之和即 l r cnt则说明即使把当前后缀中的所有星号都看成右括号也无法匹配已经出现的左括号因此字符串一定无效返回false。如果从左到右和从右到左的两次遍历都没有出现无法匹配的情况则说明所有多余的左括号和右括号都可以通过适当地将星号看成左括号、右括号或空字符串进行匹配因此字符串是有效的括号字符串。class Solution { public: bool checkValidString(string s) { int l0,r0,cnt0,ns.length(); for(int i0;in;i) { if(s[i]()l; else if(s[i]))r; else cnt; if(rlcnt)return false; } lrcnt0; for(int in-1;i0;--i) { if(s[i]()l; else if(s[i]))r; else cnt; if(lrcnt)return false; } return true; } };