尧图网站建设 
LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Valid Parentheses有效的括号是 LeetCode 经典入门题编号 20也是本仓库中()[]{}三类括号合法性判定的标准解法示例。本文以 articles/validate-parentheses.md 为核心骨架结合 hints/validate-parentheses.md 中的进阶提示以及仓库内 13 种语言的真实提交实现完整讲解从暴力替换到栈匹配的两类解法、复杂度分析、常见陷阱与多语言工程实现细节。读完本文你将掌握括号匹配问题的 O(n) 栈解法并能在面试与生产代码中正确、稳健地实现该算法。1. 问题定义与前置知识给定一个只包含字符(、)、{、}、[、]的字符串s判断输入的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的同类型左括号。在动手实现前需要掌握以下三个基础概念栈StackLIFO后进先出数据结构支持push入栈与pop出栈操作是本题的核心工具哈希表Hash Map用字典将右括号映射到对应的左括号实现 O(1) 查找字符串遍历逐字符迭代输入串是算法的主循环。仓库中对应的多语言题解文件均以0020-valid-parentheses命名例如 python/0020-valid-parentheses.py、java/0020-valid-parentheses.java、c/0020-valid-parentheses.c 等覆盖 Python、Java、C、C、JavaScript、TypeScript、C#、Go、Kotlin、Swift、Rust、Ruby、Dart 共 13 种语言可作为学习对照。2. 解法一暴力替换法Brute Force2.1 直觉合法括号一定以匹配的成对形式出现如()、{}、[]。因此如果字符串有效就可以反复移除这些匹配对直到无对可删。若移除后字符串为空则括号正确配对否则残留未匹配字符字符串无效。2.2 算法步骤当字符串仍包含()、{}或[]时移除所有出现的这些匹配对当无法再移除任何匹配对时若字符串为空返回true否则返回false。2.3 多语言实现以下为文档给出的核心实现各语言逻辑完全一致class Solution: def isValid(self, s: str) - bool: while () in s or {} in s or [] in s: s s.replace((), ) s s.replace({}, ) s s.replace([], ) return s class Solution { public: bool isValid(string s) { while (true) { size_t pos string::npos; if ((pos s.find(())) ! string::npos) { s.erase(pos, 2); continue; } if ((pos s.find({})) ! string::npos) { s.erase(pos, 2); continue; } if ((pos s.find([])) ! string::npos) { s.erase(pos, 2); continue; } break; } return s.empty(); } };class Solution { isValid(s) { while (s.includes(()) || s.includes({}) || s.includes([])) { s s.replace((), ); s s.replace({}, ); s s.replace([], ); } return s ; } }impl Solution { pub fn is_valid(s: String) - bool { let mut s s; loop { let prev s.len(); s s.replace((), ); s s.replace({}, ); s s.replace([], ); if s.len() prev { break; } } s.is_empty() } }说明Java、C#、Go、Kotlin、Swift 等语言的写法本质相同——循环内反复查找并删除三个匹配对直到字符串长度不再变化最后判断是否为空。Rust 版本通过比较替换前后长度s.len() prev来判断是否仍存在可删除的匹配对思路值得借鉴。2.4 复杂度分析时间复杂度O(n²)。每一轮replace/find都需要扫描整个字符串最坏情况下如(((...)))这类嵌套结构每轮只删除 2 个字符共需约 n/2 轮每轮 O(n)合计 O(n²)空间复杂度O(n)。每次替换都会创建新的字符串副本。这种解法思路直观但面对长输入时性能不佳。正如 hints/validate-parentheses.md 中的 Hint 1 所指出的能否换一种数据结构来做到更优3. 解法二栈 哈希映射最优解3.1 直觉合法括号遵循最后打开的括号最先闭合的顺序——就像叠盘子一样。因此用栈追踪左括号遇到右括号时只需检查它是否与栈顶最近的左括号匹配。匹配则弹出不匹配或栈为空则字符串无效。一个合法字符串处理完毕后栈应为空。3.2 算法步骤创建一个栈用于存放左括号遍历字符串的每个字符c若是左括号将其压入栈若是右括号检查栈非空且栈顶元素是对应的左括号匹配则弹出栈顶否则直接返回false处理完所有字符后栈为空则返回true否则返回false。3.3 多语言实现以下为核心解法完整多语言版本见 articles/validate-parentheses.mdclass Solution: def isValid(self, s: str) - bool: stack [] closeToOpen { ) : (, ] : [, } : { } for c in s: if c in closeToOpen: if stack and stack[-1] closeToOpen[c]: stack.pop() else: return False else: stack.append(c) return True if not stack else Falsepublic class Solution { public boolean isValid(String s) { StackCharacter stack new Stack(); MapCharacter, Character closeToOpen new HashMap(); closeToOpen.put(), (); closeToOpen.put(], [); closeToOpen.put(}, {); for (char c : s.toCharArray()) { if (closeToOpen.containsKey(c)) { if (!stack.isEmpty() stack.peek() closeToOpen.get(c)) { stack.pop(); } else { return false; } } else { stack.push(c); } } return stack.isEmpty(); } }class Solution { public: bool isValid(string s) { std::stackchar stack; std::unordered_mapchar, char closeToOpen { {), (}, {], [}, {}, {} }; for (char c : s) { if (closeToOpen.count(c)) { if (!stack.empty() stack.top() closeToOpen[c]) { stack.pop(); } else { return false; } } else { stack.push(c); } } return stack.empty(); } };func isValid(s string) bool { pairs : map[byte]byte{ }: {, ]: [, ): (, } stack : make([]byte, 0) for _, char : range []byte(s) { pair, ok : pairs[char] if !ok { stack append(stack, char) // 左括号入栈 continue } if len(stack) 0 { // 栈空却遇到右括号 return false } if stack[len(stack)-1] ! pair { // 栈顶与右括号不匹配 return false } stack stack[:len(stack)-1] // 弹出栈顶 } return len(stack) 0 }3.4 复杂度分析时间复杂度O(n)。每个字符最多入栈、出栈各一次整体线性扫描空间复杂度O(n)。最坏情况下如((((...全为左括号栈需要存储 n 个字符。这也是 hints/validate-parentheses.md 中明确推荐的O(n) 时间 / O(n) 空间方案。4. 仓库源码级实现细节仓库中各语言的实现与文档讲解高度一致同时也展示了不同的工程风格值得对照学习。4.1 Python极简版本python/0020-valid-parentheses.py 用if c not in bracketMap判断左括号直接入栈并continue逻辑与文档版完全等价只是把左括号分支前置class Solution: def isValid(self, s: str) - bool: bracketMap {): (, ]: [, }: {} stack [] for c in s: if c not in bracketMap: stack.append(c) continue if not stack or stack[-1] ! bracketMap[c]: return False stack.pop() return not stack4.2 C从零手写链式栈c/0020-valid-parentheses.c 因标准库不直接提供栈容器完整实现了基于单链表的栈结构Node链表节点、Stack栈头 长度、append压栈、pop弹栈、freeStack释放内存并用opposite_parenthesis函数完成右括号到左括号的映射。其中pop返回NULL作为空栈哨兵主循环对非法右括号直接返回false最终以stack-len 0判断结果——这是一个不依赖任何第三方库的教科书式栈实现适合理解栈的底层原理。4.3 Rustmatch 分支 迭代器rust/0020-valid-parentheses.rs 用match对(、[、{直接压栈其余字符走_分支与HashMap比对最后返回stack.is_empty()use std::collections::HashMap; impl Solution { pub fn is_valid(s: String) - bool { let mut stack: Vecchar Vec::new(); let opening HashMap::from([(], [), (), (), (}, {)]); for c in s.chars() { match c { ( stack.push(c), [ stack.push(c), { stack.push(c), _ { if stack.iter().last() opening.get(c) { stack.pop(); } else { return false; } } } } stack.is_empty() } }4.4 JavaScript两种风格javascript/0020-valid-parentheses.js 给出了两种实现第一种在遇到左括号时直接压入对应的右括号闭合时弹出比对省去了映射表第二种使用map哈希表与文档主解法一致。两种写法均为 O(n) 时间 / O(n) 空间注释中标明了每步的时空开销。4.5 Java 的奇偶长度剪枝java/0020-valid-parentheses.java 在入口处先判断s.length() % 2 ! 0直接返回false——长度为奇数的字符串必然无法完全配对这是一个廉价且有效的剪枝优化文件内同时给出无哈希表的peek比较版与 HashMap 查找表版两种实现。4.6 TypeScript / Go 的边界处理typescript/0020-valid-parentheses.ts 采用闭括号在映射表中则pop比对否则压栈的写法go/0020-valid-parentheses.go 则明确先判断len(stack) 0再比对栈顶将空栈遇右括号与栈顶不匹配两种非法情况分开处理语义更清晰。从源码结构看13 种语言的实现虽风格各异手写链式栈、match 分支、奇偶剪枝、压入右括号等但核心算法完全一致用栈记录未闭合的左括号用哈希表建立右括号到左括号的映射这正是文档所强调的统一思路。5. 常见陷阱与排查清单5.1 弹出前未检查栈是否为空遇到右括号时必须先确认栈非空再检查栈顶元素。对空栈执行pop会导致运行时错误或返回错误结果。# Wrong: crashes on empty stack if stack[-1] closeToOpen[c]: # Correct: check stack first if stack and stack[-1] closeToOpen[c]:5.2 结尾忘记检查栈是否为空处理完所有字符后可能仍有左括号未闭合。例如(()全程不会报错但栈中残留(因此字符串无效。必须以return stack.isEmpty()或等价写法收尾这是最容易被遗漏的一步。5.3 混淆映射方向构建映射时必须让右括号映射到对应的左括号方向反了会导致查找逻辑完全错误查找动作应发生在遇到右括号时。# Correct mapping: closing - opening closeToOpen {): (, ]: [, }: {}5.4 选错数据结构括号匹配遵循 LIFO后进先出顺序——最近的左括号必须最先闭合因此必须使用栈。若误用队列FIFO则顺序完全相反无法正确校验嵌套结构。6. 总结解法思路时间复杂度空间复杂度适用场景暴力替换反复删除()、{}、[]O(n²)O(n)理解题意、快速验证栈 哈希映射栈追踪未闭合左括号映射表 O(1) 匹配O(n)O(n)面试与生产首选Valid Parentheses是栈 哈希表组合的经典入门题其解法可直接迁移到更多场景字符串去重Remove All Adjacent Duplicates、表达式求值Evaluate Reverse Polish Notation、括号生成与最长有效括号等。建议对照本仓库 13 种语言的 0020-valid-parentheses 系列实现 逐一阅读并结合 hints/validate-parentheses.md 中的三条提示复杂度目标、栈思路、栈空判定自测掌握程度。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 0020 Valid Parentheses：基于栈的括号匹配校验算法全解析（多语言实现）
LeetCode 0020 Valid Parentheses基于栈的括号匹配校验算法全解析多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Valid Parentheses有效的括号是 LeetCode 经典入门题编号 20也是本仓库中()[]{}三类括号合法性判定的标准解法示例。本文以 articles/validate-parentheses.md 为核心骨架结合 hints/validate-parentheses.md 中的进阶提示以及仓库内 13 种语言的真实提交实现完整讲解从暴力替换到栈匹配的两类解法、复杂度分析、常见陷阱与多语言工程实现细节。读完本文你将掌握括号匹配问题的 O(n) 栈解法并能在面试与生产代码中正确、稳健地实现该算法。1. 问题定义与前置知识给定一个只包含字符(、)、{、}、[、]的字符串s判断输入的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的同类型左括号。在动手实现前需要掌握以下三个基础概念栈StackLIFO后进先出数据结构支持push入栈与pop出栈操作是本题的核心工具哈希表Hash Map用字典将右括号映射到对应的左括号实现 O(1) 查找字符串遍历逐字符迭代输入串是算法的主循环。仓库中对应的多语言题解文件均以0020-valid-parentheses命名例如 python/0020-valid-parentheses.py、java/0020-valid-parentheses.java、c/0020-valid-parentheses.c 等覆盖 Python、Java、C、C、JavaScript、TypeScript、C#、Go、Kotlin、Swift、Rust、Ruby、Dart 共 13 种语言可作为学习对照。2. 解法一暴力替换法Brute Force2.1 直觉合法括号一定以匹配的成对形式出现如()、{}、[]。因此如果字符串有效就可以反复移除这些匹配对直到无对可删。若移除后字符串为空则括号正确配对否则残留未匹配字符字符串无效。2.2 算法步骤当字符串仍包含()、{}或[]时移除所有出现的这些匹配对当无法再移除任何匹配对时若字符串为空返回true否则返回false。2.3 多语言实现以下为文档给出的核心实现各语言逻辑完全一致class Solution: def isValid(self, s: str) - bool: while () in s or {} in s or [] in s: s s.replace((), ) s s.replace({}, ) s s.replace([], ) return s class Solution { public: bool isValid(string s) { while (true) { size_t pos string::npos; if ((pos s.find(())) ! string::npos) { s.erase(pos, 2); continue; } if ((pos s.find({})) ! string::npos) { s.erase(pos, 2); continue; } if ((pos s.find([])) ! string::npos) { s.erase(pos, 2); continue; } break; } return s.empty(); } };class Solution { isValid(s) { while (s.includes(()) || s.includes({}) || s.includes([])) { s s.replace((), ); s s.replace({}, ); s s.replace([], ); } return s ; } }impl Solution { pub fn is_valid(s: String) - bool { let mut s s; loop { let prev s.len(); s s.replace((), ); s s.replace({}, ); s s.replace([], ); if s.len() prev { break; } } s.is_empty() } }说明Java、C#、Go、Kotlin、Swift 等语言的写法本质相同——循环内反复查找并删除三个匹配对直到字符串长度不再变化最后判断是否为空。Rust 版本通过比较替换前后长度s.len() prev来判断是否仍存在可删除的匹配对思路值得借鉴。2.4 复杂度分析时间复杂度O(n²)。每一轮replace/find都需要扫描整个字符串最坏情况下如(((...)))这类嵌套结构每轮只删除 2 个字符共需约 n/2 轮每轮 O(n)合计 O(n²)空间复杂度O(n)。每次替换都会创建新的字符串副本。这种解法思路直观但面对长输入时性能不佳。正如 hints/validate-parentheses.md 中的 Hint 1 所指出的能否换一种数据结构来做到更优3. 解法二栈 哈希映射最优解3.1 直觉合法括号遵循最后打开的括号最先闭合的顺序——就像叠盘子一样。因此用栈追踪左括号遇到右括号时只需检查它是否与栈顶最近的左括号匹配。匹配则弹出不匹配或栈为空则字符串无效。一个合法字符串处理完毕后栈应为空。3.2 算法步骤创建一个栈用于存放左括号遍历字符串的每个字符c若是左括号将其压入栈若是右括号检查栈非空且栈顶元素是对应的左括号匹配则弹出栈顶否则直接返回false处理完所有字符后栈为空则返回true否则返回false。3.3 多语言实现以下为核心解法完整多语言版本见 articles/validate-parentheses.mdclass Solution: def isValid(self, s: str) - bool: stack [] closeToOpen { ) : (, ] : [, } : { } for c in s: if c in closeToOpen: if stack and stack[-1] closeToOpen[c]: stack.pop() else: return False else: stack.append(c) return True if not stack else Falsepublic class Solution { public boolean isValid(String s) { StackCharacter stack new Stack(); MapCharacter, Character closeToOpen new HashMap(); closeToOpen.put(), (); closeToOpen.put(], [); closeToOpen.put(}, {); for (char c : s.toCharArray()) { if (closeToOpen.containsKey(c)) { if (!stack.isEmpty() stack.peek() closeToOpen.get(c)) { stack.pop(); } else { return false; } } else { stack.push(c); } } return stack.isEmpty(); } }class Solution { public: bool isValid(string s) { std::stackchar stack; std::unordered_mapchar, char closeToOpen { {), (}, {], [}, {}, {} }; for (char c : s) { if (closeToOpen.count(c)) { if (!stack.empty() stack.top() closeToOpen[c]) { stack.pop(); } else { return false; } } else { stack.push(c); } } return stack.empty(); } };func isValid(s string) bool { pairs : map[byte]byte{ }: {, ]: [, ): (, } stack : make([]byte, 0) for _, char : range []byte(s) { pair, ok : pairs[char] if !ok { stack append(stack, char) // 左括号入栈 continue } if len(stack) 0 { // 栈空却遇到右括号 return false } if stack[len(stack)-1] ! pair { // 栈顶与右括号不匹配 return false } stack stack[:len(stack)-1] // 弹出栈顶 } return len(stack) 0 }3.4 复杂度分析时间复杂度O(n)。每个字符最多入栈、出栈各一次整体线性扫描空间复杂度O(n)。最坏情况下如((((...全为左括号栈需要存储 n 个字符。这也是 hints/validate-parentheses.md 中明确推荐的O(n) 时间 / O(n) 空间方案。4. 仓库源码级实现细节仓库中各语言的实现与文档讲解高度一致同时也展示了不同的工程风格值得对照学习。4.1 Python极简版本python/0020-valid-parentheses.py 用if c not in bracketMap判断左括号直接入栈并continue逻辑与文档版完全等价只是把左括号分支前置class Solution: def isValid(self, s: str) - bool: bracketMap {): (, ]: [, }: {} stack [] for c in s: if c not in bracketMap: stack.append(c) continue if not stack or stack[-1] ! bracketMap[c]: return False stack.pop() return not stack4.2 C从零手写链式栈c/0020-valid-parentheses.c 因标准库不直接提供栈容器完整实现了基于单链表的栈结构Node链表节点、Stack栈头 长度、append压栈、pop弹栈、freeStack释放内存并用opposite_parenthesis函数完成右括号到左括号的映射。其中pop返回NULL作为空栈哨兵主循环对非法右括号直接返回false最终以stack-len 0判断结果——这是一个不依赖任何第三方库的教科书式栈实现适合理解栈的底层原理。4.3 Rustmatch 分支 迭代器rust/0020-valid-parentheses.rs 用match对(、[、{直接压栈其余字符走_分支与HashMap比对最后返回stack.is_empty()use std::collections::HashMap; impl Solution { pub fn is_valid(s: String) - bool { let mut stack: Vecchar Vec::new(); let opening HashMap::from([(], [), (), (), (}, {)]); for c in s.chars() { match c { ( stack.push(c), [ stack.push(c), { stack.push(c), _ { if stack.iter().last() opening.get(c) { stack.pop(); } else { return false; } } } } stack.is_empty() } }4.4 JavaScript两种风格javascript/0020-valid-parentheses.js 给出了两种实现第一种在遇到左括号时直接压入对应的右括号闭合时弹出比对省去了映射表第二种使用map哈希表与文档主解法一致。两种写法均为 O(n) 时间 / O(n) 空间注释中标明了每步的时空开销。4.5 Java 的奇偶长度剪枝java/0020-valid-parentheses.java 在入口处先判断s.length() % 2 ! 0直接返回false——长度为奇数的字符串必然无法完全配对这是一个廉价且有效的剪枝优化文件内同时给出无哈希表的peek比较版与 HashMap 查找表版两种实现。4.6 TypeScript / Go 的边界处理typescript/0020-valid-parentheses.ts 采用闭括号在映射表中则pop比对否则压栈的写法go/0020-valid-parentheses.go 则明确先判断len(stack) 0再比对栈顶将空栈遇右括号与栈顶不匹配两种非法情况分开处理语义更清晰。从源码结构看13 种语言的实现虽风格各异手写链式栈、match 分支、奇偶剪枝、压入右括号等但核心算法完全一致用栈记录未闭合的左括号用哈希表建立右括号到左括号的映射这正是文档所强调的统一思路。5. 常见陷阱与排查清单5.1 弹出前未检查栈是否为空遇到右括号时必须先确认栈非空再检查栈顶元素。对空栈执行pop会导致运行时错误或返回错误结果。# Wrong: crashes on empty stack if stack[-1] closeToOpen[c]: # Correct: check stack first if stack and stack[-1] closeToOpen[c]:5.2 结尾忘记检查栈是否为空处理完所有字符后可能仍有左括号未闭合。例如(()全程不会报错但栈中残留(因此字符串无效。必须以return stack.isEmpty()或等价写法收尾这是最容易被遗漏的一步。5.3 混淆映射方向构建映射时必须让右括号映射到对应的左括号方向反了会导致查找逻辑完全错误查找动作应发生在遇到右括号时。# Correct mapping: closing - opening closeToOpen {): (, ]: [, }: {}5.4 选错数据结构括号匹配遵循 LIFO后进先出顺序——最近的左括号必须最先闭合因此必须使用栈。若误用队列FIFO则顺序完全相反无法正确校验嵌套结构。6. 总结解法思路时间复杂度空间复杂度适用场景暴力替换反复删除()、{}、[]O(n²)O(n)理解题意、快速验证栈 哈希映射栈追踪未闭合左括号映射表 O(1) 匹配O(n)O(n)面试与生产首选Valid Parentheses是栈 哈希表组合的经典入门题其解法可直接迁移到更多场景字符串去重Remove All Adjacent Duplicates、表达式求值Evaluate Reverse Polish Notation、括号生成与最长有效括号等。建议对照本仓库 13 种语言的 0020-valid-parentheses 系列实现 逐一阅读并结合 hints/validate-parentheses.md 中的三条提示复杂度目标、栈思路、栈空判定自测掌握程度。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考