1. 题目解析与核心思路leetcode678是一道关于字符串有效性的算法题题目要求判断包含三种字符(、)和的字符串是否满足括号匹配规则。其中可以视为左括号、右括号或空字符。这道题在2023年字节跳动校招笔试中出现过是栈和动态规划结合的经典例题。字符串有效性的判定需要满足两个条件任何前缀中左括号的数量不少于右括号的数量整个字符串中左括号和右括号的数量相等关键难点在于通配符*的多义性处理这使简单的栈方法无法直接适用。我在实际面试中遇到过至少3次这个问题的变种。2. 双栈解法实现细节2.1 数据结构设计采用双栈结构分别存储左括号和星号的位置索引left_stack [] # 存储(的索引 star_stack [] # 存储*的索引这种设计可以在遇到右括号时优先消耗左括号当左括号不足时用星号替代最后处理剩余的左括号和星号匹配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循环有两个易错点必须确保星号在左括号右侧才能匹配循环终止条件要同时判断两个栈非空3.2 复杂度分析时间复杂度O(n) 只需一次遍历和最多一次栈处理 空间复杂度O(n) 最坏情况下需要存储所有字符索引4. 动态规划解法对比4.1 DP状态定义定义dp[i][j]表示前i个字符中左括号比右括号多j个的可能性j的范围是[0, n]因为最多可能有n个左括号未匹配初始化dp[0][0] True4.2 状态转移方程for i in range(1, n1): for j in range(n1): 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][j1] if j n else False else: dp[i][j] dp[i-1][j-1] or dp[i-1][j1] or dp[i-1][j]DP解法在面试中要求解释清楚状态定义和转移逻辑我曾被面试官连续追问了5层为什么这样设计状态。5. 常见错误与测试用例5.1 典型错误案例忽略星号的三种可能性处理剩余栈元素时顺序错误DP解法中j的范围设置不当5.2 必备测试用例测试用例集 1. () → True 2. (*) → True 3. (*)) → True 4. ((*) → False 5. *)(* → False 6. → True 7. (((*** → True 8. )*( → False6. 算法优化与变种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 06.2 变种题目只有(和)的基础版本leetcode20需要输出所有有效字符串的变种*只能代表左括号或右括号的限制条件我在实际刷题中发现掌握这道题的多种解法可以帮助快速解决至少5种相关的括号匹配问题。特别是在处理通配符场景时双栈法的思路可以扩展到其他符号匹配场景。 
长河君 · 2026/11/6 2:51:58 · 阅读 1.2k LeetCode678：通配符括号匹配的双栈与动态规划解法
1. 题目解析与核心思路leetcode678是一道关于字符串有效性的算法题题目要求判断包含三种字符(、)和的字符串是否满足括号匹配规则。其中可以视为左括号、右括号或空字符。这道题在2023年字节跳动校招笔试中出现过是栈和动态规划结合的经典例题。字符串有效性的判定需要满足两个条件任何前缀中左括号的数量不少于右括号的数量整个字符串中左括号和右括号的数量相等关键难点在于通配符*的多义性处理这使简单的栈方法无法直接适用。我在实际面试中遇到过至少3次这个问题的变种。2. 双栈解法实现细节2.1 数据结构设计采用双栈结构分别存储左括号和星号的位置索引left_stack [] # 存储(的索引 star_stack [] # 存储*的索引这种设计可以在遇到右括号时优先消耗左括号当左括号不足时用星号替代最后处理剩余的左括号和星号匹配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循环有两个易错点必须确保星号在左括号右侧才能匹配循环终止条件要同时判断两个栈非空3.2 复杂度分析时间复杂度O(n) 只需一次遍历和最多一次栈处理 空间复杂度O(n) 最坏情况下需要存储所有字符索引4. 动态规划解法对比4.1 DP状态定义定义dp[i][j]表示前i个字符中左括号比右括号多j个的可能性j的范围是[0, n]因为最多可能有n个左括号未匹配初始化dp[0][0] True4.2 状态转移方程for i in range(1, n1): for j in range(n1): 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][j1] if j n else False else: dp[i][j] dp[i-1][j-1] or dp[i-1][j1] or dp[i-1][j]DP解法在面试中要求解释清楚状态定义和转移逻辑我曾被面试官连续追问了5层为什么这样设计状态。5. 常见错误与测试用例5.1 典型错误案例忽略星号的三种可能性处理剩余栈元素时顺序错误DP解法中j的范围设置不当5.2 必备测试用例测试用例集 1. () → True 2. (*) → True 3. (*)) → True 4. ((*) → False 5. *)(* → False 6. → True 7. (((*** → True 8. )*( → False6. 算法优化与变种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 06.2 变种题目只有(和)的基础版本leetcode20需要输出所有有效字符串的变种*只能代表左括号或右括号的限制条件我在实际刷题中发现掌握这道题的多种解法可以帮助快速解决至少5种相关的括号匹配问题。特别是在处理通配符场景时双栈法的思路可以扩展到其他符号匹配场景。