描述
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例
提交的代码
import java.util.Deque;
import java.util.LinkedList;
class Solution {
public boolean isValid(String s) {
//剪枝操作
if(s.length()%2==1)return false;
Deque<Character> stack=new LinkedList<>();
char curChar=0;
for(int i=0;i<s.length();i++){
curChar=s.charAt(i);
if(curChar=='('){
stack.push(')');
}else if(curChar=='['){
stack.push(']');
}else if(curChar=='{'){
stack.push('}');
}else if(stack.isEmpty()||stack.peek()!=curChar){
return false;
}else{
stack.pop();
}
}
return stack.isEmpty();
}
}
思想:
用栈的思想来解决此问题,当遇到第一个左括号的时候,左括号入栈并且“迫切”一个右括号来消融它,如果下一个正好是相应的右括号,那么左括号出栈;若下一个元素是另一个左括号,那么前一个左括号“迫切”找到另一个右括号消融就需要降优先级,当前左括号入栈;循环此动作,直到当前字符串遍历完毕并且栈空,返回true。
试想一下,如果左括号多了一个,那么最后的结果就是遍历结束但在栈中不为空,此时返回false;如果右括号多了一个,会出现消融左括号的时候,发现栈中并没有相应的左括号并且栈为空,此时返回false;如果此时栈不为空,但是遍历到一个右括号的时候,发现栈顶元素左括号并不和当前右括号匹配,此时返回false。