1. 题目解析与核心思路

leetcode678是一道关于字符串有效性的算法题，题目要求判断包含三种字符（'('、')'和''）的字符串是否满足括号匹配规则。其中''可以视为左括号、右括号或空字符。这道题在2023年字节跳动校招笔试中出现过，是栈和动态规划结合的经典例题。

字符串有效性的判定需要满足两个条件：

1. 任何前缀中左括号的数量不少于右括号的数量
2. 整个字符串中左括号和右括号的数量相等

关键难点在于通配符'*'的多义性处理，这使简单的栈方法无法直接适用。我在实际面试中遇到过至少3次这个问题的变种。

2. 双栈解法实现细节

2.1 数据结构设计

采用双栈结构分别存储左括号和星号的位置索引：

left_stack = [] # 存储'('的索引 star_stack = [] # 存储'*'的索引

这种设计可以：

1. 在遇到右括号时优先消耗左括号
2. 当左括号不足时用星号替代
3. 最后处理剩余的左括号和星号匹配

2.2 遍历处理流程

遍历字符串时的处理逻辑：

for i, char in enumerate(s): if char == '(': left_stack.append(i) elif char == '*': star_stack.append(i) else: if left_stack: left_stack.pop() elif star_stack: star_stack.pop() else: return False

实际编码时容易忽略索引存储的顺序性，我曾因此导致一个隐蔽的bug：应该用append()和pop()维护栈结构，而不是随意操作列表。

3. 边界条件处理技巧

3.1 剩余括号匹配

遍历结束后需要处理栈中剩余元素：

while left_stack and star_stack: if left_stack[-1] < star_stack[-1]: left_stack.pop() star_stack.pop() else: break

这个while循环有两个易错点：

1. 必须确保星号在左括号右侧才能匹配
2. 循环终止条件要同时判断两个栈非空

3.2 复杂度分析

时间复杂度：O(n) 只需一次遍历和最多一次栈处理 空间复杂度：O(n) 最坏情况下需要存储所有字符索引

4. 动态规划解法对比

4.1 DP状态定义

定义dp[i][j]表示前i个字符中左括号比右括号多j个的可能性：

• j的范围是[0, n]因为最多可能有n个左括号未匹配
• 初始化dp[0][0] = True

4.2 状态转移方程

for i in range(1, n+1): for j in range(n+1): if s[i-1] == '(': dp[i][j] = dp[i-1][j-1] if j > 0 else False elif s[i-1] == ')': dp[i][j] = dp[i-1][j+1] if j < n else False else: dp[i][j] = dp[i-1][j-1] or dp[i-1][j+1] or dp[i-1][j]

DP解法在面试中要求解释清楚状态定义和转移逻辑，我曾被面试官连续追问了5层为什么这样设计状态。

5. 常见错误与测试用例

5.1 典型错误案例

1. 忽略星号的三种可能性
2. 处理剩余栈元素时顺序错误
3. DP解法中j的范围设置不当

5.2 必备测试用例

测试用例集： 1. "()" → True 2. "(*)" → True 3. "(*))" → True 4. "((*)" → False 5. "*)(*" → False 6. "" → True 7. "(((***" → True 8. ")*(" → False

6. 算法优化与变种

6.1 贪心算法优化

维护可能的最小和最大未匹配左括号数：

low = high = 0 for c in s: if c == '(': low += 1 high += 1 elif c == ')': low = max(low-1, 0) high -= 1 else: low = max(low-1, 0) high += 1 if high < 0: return False return low == 0

6.2 变种题目

1. 只有'('和')'的基础版本（leetcode20）
2. 需要输出所有有效字符串的变种
3. '*'只能代表左括号或右括号的限制条件

我在实际刷题中发现，掌握这道题的多种解法可以帮助快速解决至少5种相关的括号匹配问题。特别是在处理通配符场景时，双栈法的思路可以扩展到其他符号匹配场景。