首页 > 代码库 > LeetCode | #20 Valid Parentheses
LeetCode | #20 Valid Parentheses
题目：
Given a string containing just the characters ‘(‘, ‘)‘, ‘{‘, ‘}‘, ‘[‘ and ‘]‘, determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
- “([])”这样的形式也是valid，用栈，后进先出，判断规则如下：
- 如果是‘(‘, ‘[‘, ‘{‘，就直接入栈；
- 如果是‘)‘, ‘]‘, ‘}‘，就判断栈顶和该字符是不是一对，是就将栈顶pop，继续1，否则就返回false；
- 如果最后栈不为空，返回false，否则返回true；
可以用map也可以不用
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class ValidParentheses {
/*//用map存对应关系
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<Character, Character>(){
{
put(')', '(');
put(']', '[');
put('}', '{');
}
};
Stack<String> stack = new Stack<>();
int n = s.length();
for(int i=0; i<n; i++){
if(stack.empty()){
stack.push(s.charAt(i));
continue;
}
if(stack.peek() == (map.get(s.charAt(i)))){
stack.pop();
}else{
stack.push(s.charAt(i));
}
}
if(stack.empty())
return true;
return false;
}*/
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int n = s.length();
char c;
for(int i=0; i<n; i++){
c = s.charAt(i);
if(c==')' || c==']' || c=='}'){
if(stack.empty()) return false;
char c2 = stack.peek();
if((c==')' && c2!='(') || (c==']' && c2!='[') || (c=='}' && c2!='{')){
return false;
}
stack.pop();
}else{
stack.push(c);
}
}
if(stack.empty())
return true;
return false;
}
}LeetCode | #20 Valid Parentheses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。