题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：输入：s = "()[]{}"
输出：true
示例 3：输入：s = "(]"
输出：false
代码如下
public boolean isValid(String s) {
if(s.length()==0){
return true;
}
Stack<Character> stack=new Stack<>();
for (int i = 0; i < s.length(); ) {
stack.push(s.charAt(i));
i++;
while((!stack.isEmpty())&&(i<s.length())&&((s.charAt(i)==')'&&stack.peek()=='(')||(s.charAt(i)=='}'&&stack.peek()=='{')||(s.charAt(i)==']'&&stack.peek()=='['))){
stack.pop();
i++;
}
}
return stack.isEmpty();
}题解采用了一种逆向思维：即遍历到左半部分括号时，向栈中压入对应的右半部分，那么就可通过是否相等来判断（虽然本质是一样的hhh）
public boolean isValid(String s) {
if(s.length()==0){
return true;
}
Stack<Character> stack=new Stack<>();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)=='('){
stack.push(')');
}else if(s.charAt(i)=='['){
stack.push(']');
}else if(s.charAt(i)=='{'){
stack.push('}');
}else if(stack.isEmpty()||stack.peek()!=s.charAt(i)){
return false;//这里考虑后面会有尾巴的情况
}else{
stack.pop();
}
}
return stack.isEmpty();
}
您可能感兴趣的文章: