一.题目描述
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
二.示例
示例 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。