【LetMeFly】678.有效的括号字符串O(n)O(1)一次遍历力扣题目链接https://leetcode.cn/problems/valid-parenthesis-string/给你一个只包含三种字符的字符串支持的字符类型分别是(、)和*。请你检验这个字符串是否为有效字符串如果是有效字符串返回true。有效字符串符合如下规则任何左括号(必须有相应的右括号)。任何右括号)必须有相应的左括号(。左括号(必须在对应的右括号之前)。*可以被视为单个右括号)或单个左括号(或一个空字符串。示例 1输入s ()输出true示例 2输入s (*)输出true示例 3输入s (*))输出true提示1 s.length 100s[i]为(、)或*解题方法一次遍历使用两个变量mx和mn分别表示遍历到当前字符为止左括号比右括号最多多几个、最少多几个。遇到(则左括号必须比右括号多一个mx, mn遇到)则左括号必须比右括号少一个mx--, mn--遇到*时候*可以变成左括号mx可以变成右括号mn--也可以变成空字符一旦左括号比右括号最多多负数个说明不论怎样左括号都比右括号少了则立刻返回false如果mn 0则不再将mn - 1因为要保证左括号始终≥右括号二者数量相等的时候*不能变成)。最终如果mn 0则说明左括号比右括号最少多0个说明可以通过将*变成)来使得左右括号数量相等。时间复杂度O ( l e n ( s ) ) O(len(s))O(len(s))空间复杂度O ( 1 ) O(1)O(1)AC代码C/* * LastEditTime: 2026-10-04 17:59:19 */classSolution{public:boolcheckValidString(conststrings){intmx0,mn0;for(charc:s){if(c(){mx,mn;}elseif(c)){mx--,mn--;if(mx0){returnfalse;}}else{mx,mn--;}mnmax(mn,0);}return!mn;}};End同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源