- SomeBottle2026-10-04
力扣 LeetCode
678. 有效的括号字符串 - 力扣（LeetCode）
678. 有效的括号字符串 - 给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。
有效 字符串符合如下规则：
- 任何左括号 '(' 必须有相应的右括号 ')'。
- 任何右括号 ')' 必须有相应的左括号 '(' 。
- 左括号 '(' 必须在对应的右括号之前 ')'。
- '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串 ""。
示例...
思路
和昨天那题一样可以两趟扫描完成。不同的是这题新引入了星号
*，其可以消失（空字符串），也可以充当左括号或者右括号。从左往右扫描时，和昨天那题一样，我们关注右括号是不是过多了，这个时候的判断标准就是 右括号数量 > 左括号数量 + 星号数量，满足这个条件时肯定无法满足括号闭合。
从右往左扫描的情况依此类推。
代码```
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;
}
};主楼 - tiansuohaoer2026-10-04
贪心地把左括号和右括号填满，如果是奇数就留个*```
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;
}
}; - Lvvvv2026-10-04
两趟```
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;
}
}; - 咪帕2026-10-04
栈解法```
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();
}
};