Leetcode每日一题 —— 678. 有效的括号字符串

SomeBottle 2026-10-04 09:52 1

思路

和昨天那题一样可以两趟扫描完成。不同的是这题新引入了星号 *，其可以消失（空字符串），也可以充当左括号或者右括号。

从左往右扫描时，和昨天那题一样，我们关注右括号是不是过多了，这个时候的判断标准就是 右括号数量 > 左括号数量 + 星号数量，满足这个条件时肯定无法满足括号闭合。

从右往左扫描的情况依此类推。

代码

class Solution {

public:

    bool checkValidString(string s) {

        // * 可以弥补一次失配

        // 根据 * 和左右括号数量来判断即可

        int n=s.size();

        int left=0;

        int right=0;

        int aster=0; // 计数星号数量

        for(int i=0;i<n;i++){

            if(s[i]=='*'){

                aster++;

            }else if(s[i]=='('){

                left++;

            }else{

                right++;

            }

            // 当右括号数量大于左括号加星号数量时就无力回天了

            if(right>left+aster){

                return false;

            }

        }

        // 倒着再扫描一遍

        left=0;

        right=0;

        aster=0;

        for(int i=n-1;i>=0;i--){

            if(s[i]=='*'){

                aster++;

            }else if(s[i]=='('){

                left++;

            }else{

                right++;

            }

            // 倒着扫描就看有没有左括号大于右括号和星号数量的时候

            if(left>right+aster){

                return false;

            }

        }

        return true;

    }

};

最新回复 (3)

tiansuohaoer 10-04 10:49

1楼

贪心地把左括号和右括号填满，如果是奇数就留个*

class Solution {

public:

    bool checkValidString(string s) {

        int n=s.size(),li=n/2,p=0;

        for(auto c:s)if(c=='(')li--;

        for(auto c:s){

            if(c=='*'){

                if(li>0)li--,c='(';

                else if(n&1)n--;

                else c=')';

            }

            if(c=='(')p++;

            if(c==')')p--;

            if(p<0)return 0;

        }

        return !p;

    }

};

Lvvvv 10-04 10:51

2楼

两趟

class Solution {

public:

    bool checkValidString(string s) {

        int buffer_count = 0,diff = 0;

        int n = s.size();

        for(int i = 0; i < n; i++) {

            if(s[i] == '*') {

                buffer_count++;

            } else if(s[i] == '(') {

                diff++;

            } else {

                diff--;

            }

            if(diff + buffer_count < 0) {

                return false;

            }

        }

        if(abs(diff) > buffer_count) {

            return false;

        }

        buffer_count = 0, diff = 0;

        for(int i = n - 1; i >= 0; i--) {

            if(s[i] == '*') {

                buffer_count++;

            } else if(s[i] == ')') {

                diff++;

            } else {

                diff--;

            }

            if(diff + buffer_count < 0) {

                return false;

            }

        }

        if(abs(diff) > buffer_count) {

            return false;

        }

        return true;

    }

};

咪帕 10-04 13:02

3楼

栈解法

class Solution {

public:

    bool checkValidString(string s) {

        stack<int> lb, st;



        for (int i = 0; i < s.size(); i++) {

            if (s[i] == '(') {

                lb.push(i);

            } else if (s[i] == '*') {

                st.push(i);

            } else {

                if (!lb.empty()) {

                    lb.pop();

                } else if (!st.empty()) {

                    st.pop();

                } else {

                    return false;

                }

            }

        }



        while (!lb.empty() && !st.empty()) {

            if (lb.top() > st.top()) return false;

            lb.pop();

            st.pop();

        }



        return lb.empty();

    }

};

* 帖子来源Linux.do

附近帖子