本文详解括号匹配问题的核心逻辑与常见误区，重点指出暴力配对法的致命缺陷，并完整演示基于栈的正确实现方案，涵盖边界处理、嵌套支持及时间空间复杂度分析。
本文详解括号匹配问题的核心逻辑与常见误区，重点指出暴力配对法的致命缺陷，并完整演示基于栈的正确实现方案，涵盖边界处理、嵌套支持及时间空间复杂度分析。
括号有效性验证是经典的算法入门题，要求判断仅含 (), {}, [] 的字符串是否满足：同类型匹配、顺序正确、完全闭合。看似简单，但直接按位置配对（如原代码中用 charAt(2*index+1) 和 charAt(2*index+2) 比较）存在根本性错误。
❌ 原方法的两大逻辑缺陷
索引越界与错位访问
s.charAt(2 * index + 1) 在 index = 0 时访问下标 1，而首对括号 "()" 中 '(' 实际位于下标 0，导致从第二个字符开始比对，必然漏判或错判。更严重的是，当 index 增大时，2 * index + 2 很快超出字符串长度（如长度为 2 时，index 最大为 0，但 2*0+2 = 2 已越界），引发 StringIndexOutOfBoundsException 或逻辑崩溃。完全无法处理嵌套与交错结构
该方法隐含“括号严格成对相邻且无嵌套”的假设。例如 "[()]" 中，'[' 与 ']' 并不相邻，中间夹着 ()；又如 "{[()]}" 存在多层嵌套。原循环仅检查固定间隔的字符，对这类结构完全失效。
✅ 正确解法：使用栈（Stack）
栈的“后进先出”特性天然契合括号的嵌套规则：遇到开括号入栈，遇到闭括号时，必须与栈顶开括号匹配，否则无效。
import java.util.*;
class Solution {
public boolean isValid(String s) {
// 边界优化：奇数长度必无效
if (s.length() % 2 != 0) return false;
Stack<character> stack = new Stack();
// 使用 Map 快速映射闭括号到对应开括号
Map<character character> pairs = new HashMap() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
// 遇到开括号：直接入栈
stack.push(c);
} else if (pairs.containsKey(c)) {
// 遇到闭括号：检查栈是否为空，且栈顶是否匹配
if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
return false;
}
}
// 字符非法（题目保证只含六种，此分支可省略）
}
// 所有开括号必须被完全匹配，栈应为空
return stack.isEmpty();
}
}</character></character>
关键注意事项
- 空栈校验不可省略：闭括号出现时若栈为空（如 ")"），说明缺少对应开括号，立即返回 false。
- 匹配后必须弹出：stack.pop() 不仅验证，还移除已匹配的开括号，确保后续闭括号与更外层开括号匹配。
- 最终栈状态决定结果：循环结束后栈非空（如 "((("），说明存在未闭合的开括号，仍为无效。
- 时间/空间复杂度：O(n) 时间遍历一次字符串；O(n) 空间最坏情况（全为开括号）。
该方案简洁、健壮，完美覆盖所有有效/无效场景，包括深度嵌套（"{{[[(())]]}}"）、混合顺序（"([{}])"）及各类边界用例。
