作者:DLDLBABY1_182 | 来源:互联网 | 2023-05-17 11:57
20. 有效的括号
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确
20. 有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([)]"
输出:false
示例 5:
输入:s = "{[]}"
输出:true
提示:
- Valid Parentheses
Easy
7344301Add to ListShare
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Constraints:
1
-
s
consists of parentheses only '()[]{}'
.
解题思路:
算法原理
栈先入后出特点恰好与本题括号排序特点一致,即若遇到左括号入栈,遇到右括号时将对应栈顶左括号出栈,则遍历完所有括号后 stack 仍然为空;
算法流程
如果 c 是左括号,则入栈 push;
否则通过哈希表判断括号对应关系,若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应,则提前返回 false。
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}
char[] str = s.toCharArray();
Stack stack = new Stack();
for (int i = 0; i