欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 资讯 > LeetCode-有效的括号(020)

LeetCode-有效的括号(020)

2025/1/7 6:24:50 来源:https://blog.csdn.net/fulai00/article/details/144934406  浏览:    关键词:LeetCode-有效的括号(020)

一.题目描述

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

二.示例 

示例 1:

输入:s = "()"输出:true示例 2:输入:s = "()[]{}"输出:true示例 3:输入:s = "(]"输出:false示例 4:输入:s = "([])"输出:true

三.提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

四.解法:

方法一:栈

遍历括号字符串 s,遇到左括号时,压入当前的左括号;遇到右括号时,弹出栈顶元素(若栈为空,直接返回 false),判断是否匹配,若不匹配,直接返回 false

也可以选择遇到左括号时,将右括号压入栈中;遇到右括号时,弹出栈顶元素(若栈为空,直接返回 false),判断是否是相等。若不匹配,直接返回 false

两者的区别仅限于括号转换时机,一个是在入栈时,一个是在出栈时。

遍历结束,若栈为空,说明括号字符串有效,返回 true;否则,返回 false

时间复杂度 O(n),空间复杂度 O(n)。其中 n 为括号字符串 s 的长度。

五.代码

Java代码

class Solution {public boolean isValid(String s) {// 使用双端队列作为栈来存储左括号Deque<Character> stk = new ArrayDeque<>();// 遍历字符串中的每个字符for (char c : s.toCharArray()) {// 如果是左括号,压入栈中if (c == '(' || c == '{' || c == '[') {stk.push(c);} else if (stk.isEmpty() || !match(stk.pop(), c)) {// 如果是右括号,检查栈是否为空或栈顶元素是否匹配return false;}}// 如果栈为空,说明所有括号匹配成功return stk.isEmpty();}// 辅助函数,用于检查括号是否匹配private boolean match(char l, char r) {return (l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']');}
}注释说明·栈的使用:使用 Deque 作为栈来存储左括号,方便后续匹配。·遍历字符串:逐个检查字符串中的字符。·左括号处理:如果是左括号,直接压入栈中。·右括号处理:如果是右括号,检查栈是否为空或栈顶元素是否匹配。·如果栈为空或不匹配,返回 false。·匹配检查:使用辅助函数 match 检查当前右括号是否与栈顶左括号匹配。·最终检查:遍历结束后,检查栈是否为空,若为空则所有括号匹配成功,返回 true。

🌟 关注我的CSDN博客,收获更多技术干货! 🌟

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com