 匹配，秒解「有效的括号」)
LeetCode-Book 精选题解栈与哈希表 O(1) 匹配秒解「有效的括号」【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读「有效的括号」是《Krahets 笔面试精选 88 题》中考察**栈Stack**这一基础数据结构的入门级高频题给定一个只包含(){}[]的字符串判断括号的组成是否有效。本文以 selected_coding_interview/docs/20. 有效的括号.md 为主体完整讲解「栈 哈希表」解法背后的算法原理、逐步执行流程、边界条件处理技巧与复杂度分析并结合仓库中 Python 实现 与 Java 实现 给出可直接运行的代码。读完本文你将掌握如何利用栈的先入后出特性处理配对类问题并学会用哨兵元素优雅规避空栈异常这一经典技巧。题目速览与整体思路题目要求判断括号字符串是否有效有效定义通常为左括号必须用相同类型的右括号闭合且必须以正确的顺序闭合允许嵌套如{[]}有效而([)]无效。核心观察括号的后出现的左括号先被匹配特性与栈的**先入后出LIFO**结构完全吻合——遇到左括号入栈遇到右括号时弹出栈顶左括号并检查两者是否配对。若遍历完整个字符串后栈恰好为空则说明所有括号都正确闭合。算法原理栈的配对特性 哈希表 O(1) 查询栈栈先入后出的特点与本题括号排序特点一致。若遇到左括号就入栈遇到右括号时将对应栈顶左括号出栈则遍历完所有括号后stack仍然为空即可判定为有效哈希表建立哈希表dic构建左右括号的对应关系其中key为左括号、value为右括号。这样查询两个括号是否对应只需O(1)时间复杂度无需在每次匹配时使用条件分支逐一比较代码也更简洁、更易扩展如需新增括号类型只需在哈希表中增加一条映射。算法流程逐字符遍历与即时判定按照原文档给出的流程遍历字符串s的每个字符c如果c是左括号则将其入栈push否则c是右括号通过哈希表判断括号对应关系若栈顶出栈的括号stack.pop()与当前遍历的右括号c不对应则说明括号序列非法提前返回false遍历结束后若栈中只剩下初始的哨兵元素则返回true。提前返回 false 与边界条件处理提前返回的优点在迭代过程中提前发现不符合要求的括号并返回可以省去后续无谓的遍历提升算法效率。例如s ()[]}在遍历到最后一个字符时立刻返回false无需再做任何额外检查。但边遍历边弹出的设计会引入两个必须处理的边界情况这也是本题最容易写错的地方边界一栈为空时遇到右括号若s以右括号开头如)此时栈是空的直接执行stack.pop()会抛出异常/报错。原文档给出了一个取巧方法给stack赋初值?哨兵元素同时在哈希表dic中建立key: ?、value: ?的对应关系予以配合。这样当栈为空且c为右括号时弹出的?与任何真实右括号都不匹配dic[?] ? ! c从而可以正常地提前返回false完全避开空栈异常。哨兵?只需保证不在题目给定的合法字符集内即可?、#等任意占位符都可胜任。边界二字符串以左括号结尾若s以左括号结尾如(()整个字符串可以正常遍历完毕但栈中会遗留未出栈的左括号。此时直接返回true显然是错误的。因此遍历结束后不能判断stack是否为空而要判断len(stack) 1即是否只剩初始哨兵从而正确识别存在未闭合左括号的非法序列。这两种边界处理在 Python 源码 与 Java 源码 中均有完整体现。复杂度分析时间复杂度 O(N)正确的括号组合需要完整遍历一遍s其中哈希表查询为 O(1)整体为 O(N)空间复杂度 O(N)哈希表和栈使用线性的空间大小哈希表实际只存 4 对映射可视为常数级栈在最坏情况下需容纳全部左括号为 O(N)。多语言代码实现Python 实现与文档一致的 Python 解法完整实现见 lc_20_valid_parentheses.pyclass Solution: def isValid(self, s: str) - bool: dic {{: }, [: ], (: ), ?: ?} stack [?] for c in s: if c in dic: stack.append(c) elif dic[stack.pop()] ! c: return False return len(stack) 1Java 实现与文档一致的 Java 解法完整实现见 lc_20_valid_parentheses.javaclass Solution { private static final MapCharacter,Character map new HashMapCharacter,Character(){{ put({,}); put([,]); put((,)); put(?,?); }}; public boolean isValid(String s) { if(s.length() 0 !map.containsKey(s.charAt(0))) return false; LinkedListCharacter stack new LinkedListCharacter() {{ add(?); }}; for(Character c : s.toCharArray()){ if(map.containsKey(c)) stack.addLast(c); else if(map.get(stack.removeLast()) ! c) return false; } return stack.size() 1; } }Java 版本额外做了一层优化若s非空且首字符不是左括号即首字符就是右括号直接返回false这与哨兵?的作用互为印证属于同一思路下的防御性写法。C 参考实现从仓库的 include.hpp 可以看到C 代码目录统一引入了stack、unordered_map等标准库头文件完全支持同思路的栈解法。仓库目前仅收录了该题的 Python 与 Java 两种实现此处给出可对照阅读的 C 参考写法#include stack #include string #include unordered_map using namespace std; class Solution { public: bool isValid(string s) { unordered_mapchar, char dic {{{, }}, {[, ]}, {(, )}, {?, ?}}; stackchar stk; stk.push(?); for (char c : s) { if (dic.count(c)) stk.push(c); else if (dic[stk.top()] ! c) return false; else stk.pop(); } return stk.size() 1; } };仓库源码印证与运行方式仓库中的 Python 与 Java 实现文件在题解代码基础上补齐了驱动代码Driver CodeSolution实例化后调用isValid并将结果打印输出便于本地直接运行验证。同时Python 实现顶部通过from include import *引入了 include 公共模块Java 实现则通过import include.*引入 include 公共工具类保持了与仓库其他 88 道精选题一致的工程组织方式。运行方式以 Python 为例# 在工作区根目录执行 python selected_coding_interview/codes/python/lc_20_valid_parentheses.py替换文件末尾test_input变量即可测试()、()[]{}、(]、([)]、{[]}等典型用例。举一反三栈的更多应用「有效的括号」是栈这一数据结构的经典敲门砖理解了栈顶即最近未闭合元素这一直觉后可以继续挑战仓库中的同族题目LCR 148. 验证图书取出顺序即 LeetCode 946——同样是入栈/出栈序列的判定问题解法结构与本题的出栈模拟高度相似对应代码见 lc_946_validate_stack_sequences.py最小栈LCR 147——在栈的基础上增加 O(1) 取最小值的辅助栈设计进一步体会用栈结构维护附加信息的思路。小结本题的标准解法总结为四步遇左括号入栈 → 遇右括号弹出栈顶比对 → 不匹配提前返回 false → 遍历结束检查是否只剩哨兵。借助哈希表把括号配对查询降到 O(1)借助哨兵?优雅规避空栈边界最终实现 O(N) 时间、O(N) 空间的简洁解。这份题解连同 Python、Java 可运行源码均已收录在 LeetCode-Book 仓库的 selected_coding_interview 目录下可作为刷题与面试复习的对照资料。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Book 精选题解：栈与哈希表 O(1) 匹配，秒解「有效的括号」
LeetCode-Book 精选题解栈与哈希表 O(1) 匹配秒解「有效的括号」【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读「有效的括号」是《Krahets 笔面试精选 88 题》中考察**栈Stack**这一基础数据结构的入门级高频题给定一个只包含(){}[]的字符串判断括号的组成是否有效。本文以 selected_coding_interview/docs/20. 有效的括号.md 为主体完整讲解「栈 哈希表」解法背后的算法原理、逐步执行流程、边界条件处理技巧与复杂度分析并结合仓库中 Python 实现 与 Java 实现 给出可直接运行的代码。读完本文你将掌握如何利用栈的先入后出特性处理配对类问题并学会用哨兵元素优雅规避空栈异常这一经典技巧。题目速览与整体思路题目要求判断括号字符串是否有效有效定义通常为左括号必须用相同类型的右括号闭合且必须以正确的顺序闭合允许嵌套如{[]}有效而([)]无效。核心观察括号的后出现的左括号先被匹配特性与栈的**先入后出LIFO**结构完全吻合——遇到左括号入栈遇到右括号时弹出栈顶左括号并检查两者是否配对。若遍历完整个字符串后栈恰好为空则说明所有括号都正确闭合。算法原理栈的配对特性 哈希表 O(1) 查询栈栈先入后出的特点与本题括号排序特点一致。若遇到左括号就入栈遇到右括号时将对应栈顶左括号出栈则遍历完所有括号后stack仍然为空即可判定为有效哈希表建立哈希表dic构建左右括号的对应关系其中key为左括号、value为右括号。这样查询两个括号是否对应只需O(1)时间复杂度无需在每次匹配时使用条件分支逐一比较代码也更简洁、更易扩展如需新增括号类型只需在哈希表中增加一条映射。算法流程逐字符遍历与即时判定按照原文档给出的流程遍历字符串s的每个字符c如果c是左括号则将其入栈push否则c是右括号通过哈希表判断括号对应关系若栈顶出栈的括号stack.pop()与当前遍历的右括号c不对应则说明括号序列非法提前返回false遍历结束后若栈中只剩下初始的哨兵元素则返回true。提前返回 false 与边界条件处理提前返回的优点在迭代过程中提前发现不符合要求的括号并返回可以省去后续无谓的遍历提升算法效率。例如s ()[]}在遍历到最后一个字符时立刻返回false无需再做任何额外检查。但边遍历边弹出的设计会引入两个必须处理的边界情况这也是本题最容易写错的地方边界一栈为空时遇到右括号若s以右括号开头如)此时栈是空的直接执行stack.pop()会抛出异常/报错。原文档给出了一个取巧方法给stack赋初值?哨兵元素同时在哈希表dic中建立key: ?、value: ?的对应关系予以配合。这样当栈为空且c为右括号时弹出的?与任何真实右括号都不匹配dic[?] ? ! c从而可以正常地提前返回false完全避开空栈异常。哨兵?只需保证不在题目给定的合法字符集内即可?、#等任意占位符都可胜任。边界二字符串以左括号结尾若s以左括号结尾如(()整个字符串可以正常遍历完毕但栈中会遗留未出栈的左括号。此时直接返回true显然是错误的。因此遍历结束后不能判断stack是否为空而要判断len(stack) 1即是否只剩初始哨兵从而正确识别存在未闭合左括号的非法序列。这两种边界处理在 Python 源码 与 Java 源码 中均有完整体现。复杂度分析时间复杂度 O(N)正确的括号组合需要完整遍历一遍s其中哈希表查询为 O(1)整体为 O(N)空间复杂度 O(N)哈希表和栈使用线性的空间大小哈希表实际只存 4 对映射可视为常数级栈在最坏情况下需容纳全部左括号为 O(N)。多语言代码实现Python 实现与文档一致的 Python 解法完整实现见 lc_20_valid_parentheses.pyclass Solution: def isValid(self, s: str) - bool: dic {{: }, [: ], (: ), ?: ?} stack [?] for c in s: if c in dic: stack.append(c) elif dic[stack.pop()] ! c: return False return len(stack) 1Java 实现与文档一致的 Java 解法完整实现见 lc_20_valid_parentheses.javaclass Solution { private static final MapCharacter,Character map new HashMapCharacter,Character(){{ put({,}); put([,]); put((,)); put(?,?); }}; public boolean isValid(String s) { if(s.length() 0 !map.containsKey(s.charAt(0))) return false; LinkedListCharacter stack new LinkedListCharacter() {{ add(?); }}; for(Character c : s.toCharArray()){ if(map.containsKey(c)) stack.addLast(c); else if(map.get(stack.removeLast()) ! c) return false; } return stack.size() 1; } }Java 版本额外做了一层优化若s非空且首字符不是左括号即首字符就是右括号直接返回false这与哨兵?的作用互为印证属于同一思路下的防御性写法。C 参考实现从仓库的 include.hpp 可以看到C 代码目录统一引入了stack、unordered_map等标准库头文件完全支持同思路的栈解法。仓库目前仅收录了该题的 Python 与 Java 两种实现此处给出可对照阅读的 C 参考写法#include stack #include string #include unordered_map using namespace std; class Solution { public: bool isValid(string s) { unordered_mapchar, char dic {{{, }}, {[, ]}, {(, )}, {?, ?}}; stackchar stk; stk.push(?); for (char c : s) { if (dic.count(c)) stk.push(c); else if (dic[stk.top()] ! c) return false; else stk.pop(); } return stk.size() 1; } };仓库源码印证与运行方式仓库中的 Python 与 Java 实现文件在题解代码基础上补齐了驱动代码Driver CodeSolution实例化后调用isValid并将结果打印输出便于本地直接运行验证。同时Python 实现顶部通过from include import *引入了 include 公共模块Java 实现则通过import include.*引入 include 公共工具类保持了与仓库其他 88 道精选题一致的工程组织方式。运行方式以 Python 为例# 在工作区根目录执行 python selected_coding_interview/codes/python/lc_20_valid_parentheses.py替换文件末尾test_input变量即可测试()、()[]{}、(]、([)]、{[]}等典型用例。举一反三栈的更多应用「有效的括号」是栈这一数据结构的经典敲门砖理解了栈顶即最近未闭合元素这一直觉后可以继续挑战仓库中的同族题目LCR 148. 验证图书取出顺序即 LeetCode 946——同样是入栈/出栈序列的判定问题解法结构与本题的出栈模拟高度相似对应代码见 lc_946_validate_stack_sequences.py最小栈LCR 147——在栈的基础上增加 O(1) 取最小值的辅助栈设计进一步体会用栈结构维护附加信息的思路。小结本题的标准解法总结为四步遇左括号入栈 → 遇右括号弹出栈顶比对 → 不匹配提前返回 false → 遍历结束检查是否只剩哨兵。借助哈希表把括号配对查询降到 O(1)借助哨兵?优雅规避空栈边界最终实现 O(N) 时间、O(N) 空间的简洁解。这份题解连同 Python、Java 可运行源码均已收录在 LeetCode-Book 仓库的 selected_coding_interview 目录下可作为刷题与面试复习的对照资料。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考