LeetCode 678：有效括号字符串的栈与贪心解法

1. 题目解析LeetCode 678 有效的括号字符串LeetCode 678题有效的括号字符串是一道经典的字符串处理题目主要考察对栈数据结构的灵活运用和边界条件的处理能力。题目要求判断给定的字符串是否包含有效的括号组合其中星号(*)可以替代左括号、右括号或空字符。这类问题在实际开发中经常出现在语法检查、表达式求值等场景。1.1 问题描述与示例给定一个只包含三种字符的字符串()和*我们需要判断这个字符串是否是有效的。定义有效性规则如下任何左括号(必须有对应的右括号)任何右括号)必须有对应的左括号(星号*可以被视为单个左括号(或单个右括号)或空字符串左括号必须在对应的右括号之前出现示例1 输入() 输出true示例2 输入(*) 输出true示例3 输入(*)) 输出true1.2 核心难点分析这道题的特殊之处在于星号的多义性这使得简单的栈方法无法直接适用。我们需要考虑星号作为通配符带来的多种可能性括号嵌套时星号的作用域问题如何高效地处理星号的不同选择带来的影响2. 解决方案设计与比较2.1 暴力递归法不推荐最直观的思路是尝试所有可能的星号组合然后检查每种情况是否有效。这种方法时间复杂度为O(3^n)n是星号数量显然不适用于较长的字符串。def is_valid(s): def helper(s, start, count): if count 0: return False for i in range(start, len(s)): if s[i] (: count 1 elif s[i] ): if count 0: return False count - 1 else: # * return (helper(s, i1, count1) or # as ( helper(s, i1, count-1) or # as ) helper(s, i1, count)) # as empty return count 0 return helper(s, 0, 0)注意这种方法虽然直观但在LeetCode上会因超时无法通过所有测试用例仅适用于理解问题本质。2.2 双栈法推荐更高效的解法是使用两个栈分别记录左括号和星号的位置def is_valid(s): left_stack [] star_stack [] 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 # 处理剩余的左括号和星号 while left_stack and star_stack: if left_stack[-1] star_stack[-1]: return False left_stack.pop() star_stack.pop() return not left_stack这种方法的时间复杂度是O(n)空间复杂度也是O(n)能够高效处理长字符串。2.3 贪心算法最优解最优解法使用贪心策略只需维护两个计数器def is_valid(s): low high 0 for char in s: if char (: low 1 high 1 elif char ): low max(low - 1, 0) high - 1 if high 0: return False else: # * low max(low - 1, 0) high 1 return low 0这里low和high分别表示可能的最少和最多未匹配的左括号数。这种解法时间复杂度O(n)空间复杂度O(1)是最优解。3. 算法原理深度解析3.1 双栈法工作原理双栈法的核心思想是遇到左括号时将其位置压入left_stack遇到星号时将其位置压入star_stack遇到右括号时优先使用左括号匹配pop left_stack没有左括号则使用星号匹配pop star_stack最后检查剩余的左括号能否被星号匹配注意星号必须在左括号右边这种方法直观体现了就近匹配的原则确保括号嵌套的正确性。3.2 贪心算法数学原理贪心算法的精妙之处在于用两个变量动态跟踪可能的未匹配左括号范围low表示最少可能的未匹配左括号数将*尽可能视为右括号high表示最多可能的未匹配左括号数将*尽可能视为左括号在任何时候如果high变为负数说明右括号过多直接返回false。最终检查low是否为0确认所有左括号都能被匹配。4. 边界条件与测试用例4.1 必须考虑的边界情况空字符串应返回true全是星号应返回true右括号开头应返回false左括号过多如((*应返回false右括号过多如(*)))应返回false星号位置关键如(应返回true4.2 测试用例设计技巧设计测试用例时应考虑星号在不同位置的作用嵌套括号的深度星号连续出现的情况字符串长度极端情况空串和长串示例测试用例test_cases [ (, True), (*, True), ((*), True), ((*)), True), (((*), True), ((()*, True), (())**, False), (**(()), True), (****(((((, False), ())))****, False), ((*(), True), (()(), True) ]5. 实际应用与性能优化5.1 实际应用场景这类算法可用于代码编辑器的语法检查配置文件格式验证数学表达式解析模板语言处理任何需要灵活括号匹配的场景5.2 性能优化技巧提前终止在遍历过程中如果high变为负可立即返回false空间优化贪心算法只需常数空间是首选方案并行处理对超长字符串可考虑分段处理预处理过滤明显无效的输入如单数长度的非全星号字符串6. 常见错误与调试技巧6.1 典型错误模式忽略星号作为空字符的情况错误处理右括号先于左括号的情况未考虑星号位置对匹配的影响边界条件处理不完整如空输入贪心算法中low未取max(0, low-1)6.2 调试建议打印中间变量在贪心算法中打印low和high的变化可视化栈状态对于双栈法可以打印栈内容小规模测试先在小例子长度5上验证极端测试测试全左括号、全右括号、全星号等情况7. 算法扩展与变种7.1 类似题目LeetCode 20有效的括号基础版LeetCode 22括号生成LeetCode 32最长有效括号LeetCode 301删除无效的括号7.2 变种问题要求输出所有可能的有效括号组合星号只能作为左括号或右括号不能为空多类型括号混合如{}, [], ()加入优先级限制某些星号必须作为特定括号8. 编码实现细节8.1 Python实现注意事项使用列表模拟栈时注意pop()和append()的时间复杂度都是O(1)字符串遍历时enumerate()比range(len())更Pythonic注意字符串索引从0开始布尔值直接返回不要写if condition: return True else: return False8.2 其他语言实现Java实现示例贪心算法public boolean checkValidString(String s) { int low 0, high 0; for (char c : s.toCharArray()) { if (c () { low; high; } else if (c )) { low Math.max(low - 1, 0); high--; if (high 0) return false; } else { low Math.max(low - 1, 0); high; } } return low 0; }9. 复杂度分析与证明9.1 时间复杂度所有三种方法都需要完整遍历字符串一次暴力法最坏O(3^n)双栈法O(n)贪心法O(n)9.2 空间复杂度暴力法O(n) 递归栈空间双栈法O(n) 栈存储空间贪心法O(1) 常数空间9.3 正确性证明贪心算法的正确性基于以下观察high始终跟踪最大可能的未匹配左括号low始终跟踪最小可能的未匹配左括号任何时刻high不能为负右括号过多最终low必须为0所有左括号都能被匹配这个范围包含了所有可能的未匹配左括号数量因此是正确的。10. 学习路径建议对于想精通这类问题的开发者建议的学习顺序先掌握LeetCode 20基础括号匹配理解栈的应用场景和操作尝试解决LeetCode 678本题挑战更复杂的变种问题在实际项目中寻找类似场景应用记住这类问题的核心是理解括号匹配的本质和灵活处理通配符的能力。多练习类似题目培养对栈和贪心算法的直觉。