LeetCode 678 贪心算法
时间: 2025-02-14 08:56:57 浏览: 32
### LeetCode 678 题 贪心算法解决方案分析
#### 问题描述
LeetCode第678题名为“有效的括号字符串”,题目要求判断给定的字符串是否为有效括号串。一个有效括号串满足以下条件:
- 字符串为空;
- 或者是一个被匹配好的括号对 `()`;
- 或者是由多个上述情况组成的组合。
为了简化处理,题目引入了星号`*`作为通配字符,它可以表示左括号`(`、右括号`)`或空格。
#### 方案解析
针对这个问题,采用贪心算法的核心在于维护两个变量来追踪可能的最大和最小未闭合左括号数量。这有助于动态调整并验证整个过程中是否存在合法路径使得所有括号都得到正确匹配[^1]。
```java
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
++low;
++high;
} else if (c == ')') {
--low;
--high;
} else { // *
--low;
++high;
}
if (high < 0) break; // 提前终止条件
low = Math.max(low, 0);
}
return low == 0;
}
```
这段代码展示了如何运用贪心原则解决本题。遍历输入字符串的同时更新高低边界值,其中高边界的增加代表乐观估计——假设遇到的是最有利于形成更多开放状态的情况;而低边界的减少则反映了悲观预期下的变化趋势。当发现即使是最理想的状况也无法维持非负数目的待关闭左括号时,则立即返回失败标志。最后如果能保持至少一种情形下不存在多余未封闭的左括号,则认为该表达式是合理的[^2]。
阅读全文
相关推荐




















