题目描述
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
20. 有效的括号 - 力扣（LeetCode）
解题思路
使用栈辅助存储左括号，来进行匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public boolean isValid(String s) {
if(s.length()%2!=0)return false;
Stack<Character> stack=new Stack();
for(int i=0;i<s.length();i++){
char a=s.charAt(i);
if(a=='{'||a=='['||a=='('){
stack.push(a);
}
else{
if(stack.isEmpty()){
return false;
}
if(a=='}'){
if(stack.pop()!='{'){
return false;
}
}
else if(a==']'){
if(stack.pop()!='['){
return false;
}
}
else if(a==')'){
if(stack.pop()!='('){
return false;
}
}
}
}
if(!stack.isEmpty()){
return false;
}
return true;
}
}
|
写完通过后，看了别人的解法，可以说是相当简洁
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean isValid(String s) {
Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}
|