【每日一题】LeetCode 20.有效的括号(栈、字符串)
题目描述
给定一个只包含括号字符的字符串 s
,判断该字符串是否为有效的括号序列。一个有效的括号序列需要满足以下条件:
-
每个左括号
()
、[]
、{}
必须有一个对应的右括号与之匹配。 -
括号必须按照正确的顺序闭合,即左括号必须在右括号之前出现。
示例
输入
- 字符串
s
,长度在1
到10^4
之间,仅由括号字符()
、[]
、{}
组成。
输出
- 布尔值,如果字符串
s
是有效的括号序列,则返回true
;否则返回false
。
示例
-
输入:
s = "()"
- 输出:
true
- 解释:字符串中的括号正确闭合。
- 输出:
-
输入:
s = "()[]{}"
- 输出:
true
- 解释:字符串中的括号正确闭合。
- 输出:
-
输入:
s = "(]"
- 输出:
false
- 解释:
'('
没有被正确闭合。
- 输出:
-
输入:
s = "([])"
- 输出:
true
- 解释:字符串中的括号正确闭合。
- 输出:
思路分析
为了判断一个字符串是否是有效的括号序列,我们可以使用一个栈(Stack)来处理这个问题。栈是一种后进先出(LIFO)的数据结构,非常适合处理这种成对出现的问题。
- 遍历字符串:逐个字符遍历字符串
s
。 - 处理左括号:如果当前字符是左括号(
(
、[
、{
),则将其压入栈中。 - 处理右括号:如果当前字符是右括号(
)
、]
、}
),则需要检查栈顶元素:- 如果栈为空,或者栈顶元素与当前右括号不匹配,则说明序列无效,返回
false
。 - 如果栈顶元素与当前右括号匹配,则将栈顶元素弹出。
- 如果栈为空,或者栈顶元素与当前右括号不匹配,则说明序列无效,返回
- 最终检查:遍历完字符串后,如果栈为空,则说明所有左括号都找到了匹配的右括号,返回
true
;否则返回false
。
代码实现
class Solution {public boolean isValid(String s) {// 使用栈来存储左括号Stack<Character> stack = new Stack<>();// 遍历字符串中的每个字符for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 如果是左括号,压入栈中if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {// 如果栈为空,说明没有对应的左括号,返回 falseif (stack.isEmpty()) {return false;}// 检查栈顶元素是否与当前右括号匹配if ((c == ')' && stack.peek() != '(') ||(c == '}' && stack.peek() != '{') ||(c == ']' && stack.peek() != '[')) {return false;}// 如果匹配,则弹出栈顶元素stack.pop();}}// 如果栈为空,说明所有括号都正确闭合,返回 true;否则返回 falsereturn stack.isEmpty();}
}