有效的括号

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

有效字符串需满足:

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

示例 1:

输入:s = “()”

输出:true

示例 2:

输入:s = “()[]{}”

输出:true

示例 3:

输入:s = “(]”

输出:false

示例 4:

输入:s = “([])”

输出:true

提示:

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

利用栈来存储括号,如果是左括号直接进,如果是右括号,从栈顶检测是否有匹配的左括号,如果没有或栈为空,返回false,全部遍历完毕且栈为空,返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private char[] stack;
public boolean isValid(String s) {
if ((s.length() & 1) != 0)
return false;
stack = new char[s.length()];
int top = -1;
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put(']', '[');
map.put('}', '{');
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '{' || ch == '[') {
stack[++top] = ch;
} else {
if (top == -1 || stack[top--] != map.get(ch)) {
return false;
}
}
}
return top == -1 ? true : false;
}
}