力扣(有效括号)
LeetCode 20. 有效的括号:解析与不匹配案例全解
一、题目分析
有效的括号字符串需同时满足三个条件:
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有对应的左括号
我们需要判断一个仅包含()[]{}
的字符串是否满足这些条件。
二、算法核心思路:栈的巧妙运用
栈的"后进先出"特性与括号匹配的"最近原则"高度契合,算法核心思路如下:
- 遍历字符串:逐个处理每个括号字符
- 左括号处理:遇到左括号时,将其对应的右括号压入栈中
(
对应)
入栈[
对应]
入栈{
对应}
入栈
- 右括号处理:遇到右括号时,检查栈顶元素
- 若栈为空或栈顶元素与当前右括号不匹配,说明字符串无效
- 若匹配,则弹出栈顶元素,继续遍历
- 最终判断:遍历结束后,栈为空则字符串有效,否则无效
三、所有不匹配情况及算法处理
1. 字符串长度为奇数
案例:"(()"
、"[]}"
、"{"
原理:有效的括号必须成对出现,总长度必然为偶数。长度为奇数时,至少有一个括号无法匹配。
算法处理:
if (s.length() % 2 != 0) { return false;
}
代码开头即进行此判断,提前终止,提高效率。
2. 右括号无对应左括号
案例:")()"
、"[]))"
、")]"
原理:遍历到右括号时,栈为空(没有对应的左括号入栈),说明该右括号多余。
算法处理:
// 右括号:检查栈空或不匹配
if (stack.empty() || letter != stack.peek()) { return false;
}
如处理")()"
时,第一个字符是')'
,此时栈为空,直接返回false
。
3. 括号类型不匹配
案例:"([)]"
、"{[)]}"
、"(]"
原理:右括号与最近的左括号类型不匹配,违反"相同类型闭合"原则。
算法处理:
通过比较当前右括号与栈顶元素(预期的右括号)判断是否匹配。
以"{[)]}"
为例:
- 处理
'{'
,栈顶为'}'
- 处理
'['
,栈顶为']'
- 处理
')'
,栈顶是']'
,')' != ']'
,判定不匹配
4. 左括号未被完全匹配
案例:"(()"
、"{{[}"
、"([{"
原理:存在未被右括号匹配的左括号,遍历结束后栈中仍有剩余元素。
算法处理:
// 栈空则所有左括号匹配完成
return stack.empty();
以"(()"
为例:
- 处理
'('
,栈顶为')'
- 处理
'('
,栈顶为')'
- 处理
')'
,弹出栈顶,栈中仍剩一个')'
- 遍历结束后栈非空,返回
false
四、完整代码实现
class Solution {public boolean isValid(String s) {// 长度为奇数,直接无效if (s.length() % 2 != 0) { return false;}int len = 0;Stack<Character> stack = new Stack<>();while (len < s.length()) {char letter = s.charAt(len);// 左括号:压入对应右括号if (letter == '(') { stack.push(')');} else if (letter == '[') {stack.push(']');} else if (letter == '{') {stack.push('}');} else { // 右括号:检查栈空或不匹配if (stack.empty() || letter != stack.peek()) { return false;}// 匹配则弹出栈顶stack.pop(); }len++;}// 栈空则所有左括号匹配完成return stack.empty(); }
}
五、算法复杂度分析
- 时间复杂度:O(n),其中n是字符串长度。每个字符最多入栈和出栈各一次,均为O(1)操作
- 空间复杂度:O(n),最坏情况下(全为左括号),栈需要存储n/2个字符
有效的括号判断算法巧妙利用了栈的"后进先出"特性,通过将左括号转换为对应右括号入栈,将匹配问题转化为简单的相等判断。算法能够处理所有可能的不匹配情况:
- 长度为奇数的字符串
- 右括号无对应左括号
- 括号类型不匹配
- 左括号未被完全匹配