678.有效的括号字符串：O(n)+O(1)一次遍历

【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 <= 100
• s[i] 为 '('、')' 或 '*'

解题方法：一次遍历

使用两个变量mx和mn分别表示遍历到当前字符为止，左括号比右括号最多多几个、最少多几个。

• 遇到(则左括号必须比右括号多一个（mx++, mn++）
• 遇到)则左括号必须比右括号少一个（mx--, mn--）
• 遇到*时候*可以变成左括号（mx++），可以变成右括号（mn--），也可以变成空字符

一旦左括号比右括号最多多负数个（说明不论怎样左括号都比右括号少了）则立刻返回false；如果mn == 0则不再将mn - 1，因为要保证左括号始终≥右括号，二者数量相等的时候*不能变成)。

最终，如果mn == 0则说明左括号比右括号最少多0个，说明可以通过将*变成)来使得左右括号数量相等。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-10-04 17:59:19
 */
class Solution {
public:
    bool checkValidString(const string& s) {
        int mx = 0, mn = 0;
        for (char c : s) {
            if (c == '(') {
                mx++, mn++;
            } else if (c == ')') {
                mx--, mn--;
                if (mx < 0) {
                    return false;
                }
            } else {
                mx++, mn--;
            }
            mn = max(mn, 0);
        }
        return !mn;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源