本文介绍一种高效算法，用两个阶段扫描判断含 *（可作左括号、右括号或空字符）的字符串是否能构成合法括号序列，核心是贪心匹配与逆向补配结合。

问题核心

本文介绍一种高效算法，用两个阶段扫描判断含 *（可作左括号、右括号或空字符）的字符串是否能构成合法括号序列，核心是贪心匹配与逆向补配结合。

在 PHP 里，像 "()*"、"*)()"、"()**" 这类带有通配符 * 的括号字符串，判断它是否“可平衡”，核心在于看能否找到一种替换方案。

也就是把每个 * 改成 '('、')'，或者直接当作空字符串处理，最终让整段括号严格配对。

这个问题不能直接照搬经典的栈匹配思路。后者更适合只包含 () 的标准场景。

说白了，* 不是单一角色。它既可能在左括号不够时顶上去，也可能在左括号过多时充当右括号来抵消，必要时还可以完全忽略。

标准解法

标准解法采用两遍贪心扫描策略，兼顾可行性与完备性。

第一遍：正向扫描——尽可能匹配右括号 )

• 维护一个数组 $open 记录所有 '(' 的位置（索引）；
• 用整型 $star 统计已遇到的 * 数量；
• 遇到 ) 时：
  • 优先弹出一个 '('（array_pop($open)）；
  • 若无 '(' 可用，则消耗一个 * 作为 )（$star--）；
  • 若两者皆无，立即返回 false。
• 遇到 (：压入其位置到 $open；
• 遇到 *：$star++。

此阶段确保所有 ) 都被合法覆盖，但可能遗留未闭合的 '('。

这些剩余的左括号，必须由后续 * 来“闭合”。

第二遍：逆向扫描——为剩余 '(' 匹配右侧 *

• 将 $open 反转（array_reverse($open)），使其按从右到左顺序排列；
• 重置 $star = 0 和指针 $ptr = 0；
• 从字符串末尾向前遍历（$i = $len-1 → 0），同时遍历 $open：
  • 遇到 *：$star++；
  • 遇到某个 '('（即 $i === $open[$ptr]）：
    • 若此时 $star == 0，说明该 '(' 右侧无可用 * 作 )，返回 false；
    • 否则 --$star 并 ++$ptr，表示成功配对。

关键洞察：* 在第二遍中只作为右括号使用（因第一遍已将其尽可能用作左括号或空字符），从而避免歧义，保证逻辑唯一性。

PHP 完整实现

以下是完整、可运行的 PHP 实现：

 0) {
$star--;
} else {
return false;
}
} elseif ($char === '(') {
$open[] = $i;
} else { // $char === '*'
$star++;
}
}

// 若无剩余 '('，直接合法
if (empty($open)) {
return true;
}

// 第二遍：逆向扫描，为剩余 '(' 匹配右侧 '*'
$open = array_reverse($open);
$star = 0;
$ptr = 0;

for ($i = $len - 1; $i >= 0 && $ptr < count($open); --$i) {
if ($str[$i] === '*') {
$star++;
} elseif ($i === $open[$ptr]) {
if ($star === 0) {
return false;
}
$star--;
$ptr++;
}
}

return true;
}

// 测试用例
var_dump(isValid("()*")); // false
var_dump(isValid("()(*"));// true
var_dump(isValid("*)()"));// true
var_dump(isValid("()**"));// true
var_dump(isValid(")("));// false
var_dump(isValid(")*"));// false
?>

注意事项

• 时间复杂度 O(n)，空间复杂度 O(n)（最坏存所有 '(' 位置）；
• 不要尝试用单栈 + 多映射规则（如原提问中的 isValid() 辅助函数），易陷入状态爆炸或逻辑冲突；
• * 的灵活性必须通过分阶段职责分离来控制：第一遍保底消 )，第二遍精准补 (；
• 此算法已被 LeetCode #678 验证为最优解，适用于任意长度输入。

结论

掌握该双阶段贪心策略，即可稳健处理所有含 * 的括号校验场景。

《夸克》非常好用的免费AI浏览器

下载APP查看