本文介绍一种高效算法，用于判断包含普通括号 (、) 和通配符 ``（可代表左括号、右括号或空字符）的字符串是否能构成合法括号序列。核心思路是两次扫描：首次贪心匹配右括号，第二次逆序验证剩余左括号能否被右侧星号覆盖。
本文介绍一种高效算法，用于判断包含普通括号 `(`、`)` 和通配符 `*`（可代表左括号、右括号或空字符）的字符串是否能构成合法括号序列。核心思路是两次扫描：首次贪心匹配右括号，第二次逆序验证剩余左括号能否被右侧星号覆盖。
在处理带通配符的括号匹配问题时，传统单栈方法（如仅记录 '('）无法应对 '*' 的多义性——它既可作 '(' 补充左括号，也可作 ')' 消耗左括号，甚至可忽略。因此，需采用双阶段贪心策略，兼顾“最小可能未匹配左括号数”和“最大可能未匹配左括号数”，但本解法采用更直观的两遍扫描法，逻辑清晰且易于实现。
第一遍：正向扫描，优先消耗明确的右括号
遍历字符串，维护：
-
$open：存储所有'('出现位置的索引数组（便于后续定位）； -
$star：累计遇到的'*'数量。
对每个字符：
- 遇到
')'：优先弹出一个'('（array_pop($open)）；若无'('，则消耗一个'*'（$star--）；若两者皆无，直接返回false； - 遇到
'('：压入其索引到$open； - 遇到
'*'：$star++。
此阶段确保所有 ')' 均有对应左端支持（来自 '(' 或 '*'）。
第二遍：逆向扫描，验证剩余 '(' 是否可被右侧 '*' 匹配
若第一遍后 $open 为空，说明已完全匹配，直接返回 true。否则，需检查每个剩余 '(' 是否有 *在其右侧的 `''** 可充当')'` 与之配对。
具体做法：
- 将
$open索引数组反转（使索引从大到小排列），便于从字符串末尾向前匹配； - 从字符串最右端开始遍历，用
$ptr指向当前待匹配的'('（按位置从右到左）； - 遇到
'*'：$star++（积累可用右括号资源）； - 遇到
'('且恰好是$open[$ptr]对应位置：必须有至少一个'*'可消耗（if ($star == 0) return false; $star--; $ptr++;）； - 若
$ptr已遍历完所有'('，说明全部成功配对。
完整实现代码
<?php function isValid($str) {
$open = []; // 存储 '(' 的索引
$star = 0;
$len = strlen($str);
// 第一遍：正向扫描，处理 ')'
for ($i = 0; $i < $len; ++$i) {
switch ($str[$i]) {
case ')':
if (!empty($open)) {
array_pop($open);
} elseif ($star > 0) {
$star--;
} else {
return false; // 无 '(' 也无 * 可配对 ')'
}
break;
case '(':
$open[] = $i;
break;
case '*':
$star++;
break;
}
}
// 若无剩余 '('，直接有效
if (empty($open)) {
return true;
}
// 第二遍：逆向扫描，检查剩余 '(' 是否能被右侧 '*' 匹配
$open = array_reverse($open); // 从最右的 '(' 开始匹配
$star = 0;
$ptr = 0;
for ($i = $len - 1; $i >= 0 && $ptr
注意事项与总结
- 该算法时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况下存储所有
'('索引）； -
'*'的灵活性体现在两阶段分工：第一遍用作“兜底右括号”，第二遍用作“定向右括号”； - 切勿尝试用单栈 + 映射表（如原提问中的
$mapping）模拟所有组合，会导致状态爆炸且逻辑不可控； - 实际应用中，建议增加输入校验（如仅允许
'(',')','*'字符），避免意外行为。
通过这种结构化两遍扫描，我们既能保证正确性，又保持了代码的可读性与可维护性，是解决通配符括号匹配问题的推荐实践。
php免费学习视频：立即使用
踏上前端学习之旅，开启通往精通之路！从前端基础到项目实战，循序渐进，一步一个脚印，迈向巅峰！
