LeetCode 678：有效的括号字符串 ← 贪心算法

本文主要是介绍LeetCode 678：有效的括号字符串 ← 贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目来源】
https://leetcode.cn/problems/valid-parenthesis-string/description/

【题目描述】
给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：
● 任何左括号 '(' 必须有相应的右括号 ')'。
● 任何右括号 ')' 必须有相应的左括号 '(' 。
● 左括号 '(' 必须在对应的右括号之前 ')'。
● '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
● 一个空字符串也被视为有效字符串。

【输入输出样例】
示例1：
输入：s = "()"
输出：true

示例 2：
输入：s = "(*)"
输出：true

示例 3：
输入：s = "(*))"
输出：true

【提示】
● 1 <= s.length <= 100
● s[i] 为 '('、')' 或 '*'

【算法分析】
下文代码中的 LMax 是当前未配对的左括号 ( 的最大个数，LMin 是当前未配对的左括号 ( 的最小个数。

【算法代码】

#include <bits/stdc++.h>
using namespace std;bool check(string s) {int LMin=0;int LMax=0;for(int i=0; i<s.length(); i++) {if(s[i]=='(') {LMin++;LMax++;} else if(s[i]==')') {if(LMin>0) LMin--;LMax--;if(LMax<0) return false;} else {if(LMin>0) LMin--;LMax++;}}return LMin<=0 && LMax>=0;
}int main() {string s;while(1) {cin>>s;if(check(s)) cout<<"True"<<endl;else cout<<"False"<<endl;}return 0;
}/*
in:
()
(*)
)*(out:
True
True
False
*/

【参考文献】
https://blog.csdn.net/weixin_43750513/article/details/107597142
 

这篇关于LeetCode 678：有效的括号字符串 ← 贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---