题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([])”
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
题解1
相当经典的一道题
就是用栈
遍历s，当前为左括号时，直接入栈
当前为右括号判断栈顶元素是否为对应左括号
小点：
1、可以直接判断s长度，如果为奇数直接返回false
2、需要判断时，栈顶元素为空，直接返回false
代码：
class Solution {
public boolean isValid(String s) {
if(s.length()%2==1) return false;
Deque<Character> stack =new ArrayDeque<>();
Map<Character,Character> map=new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
int len=s.length();
for(int i=0;i<len;i++){
char ch=s.charAt(i);
if(map.containsKey(ch)){
if(stack.isEmpty()||map.get(ch)!=stack.peek()) return false;
stack.pop();
}
elsestack.push(ch);
}
return stack.isEmpty();
}
}
题解2
看了一眼最优解
发现可以用数组模拟栈
并且用s.toCharArray()作为这个栈
可以实现栈的同时在这个数组上读取数据
性能极好
class Solution {
public boolean isValid(String s) {
int len=s.length();
if(len%2==1) return false;
char[] stack = s.toCharArray();
int i=0,j=0;
while(i<len){
if(stack[i]==')'&&j>0&&stack[j-1]=='(') j--;
else if(stack[i]==']'&&j>0&&stack[j-1]=='[') j--;
else if(stack[i]=='}'&&j>0&&stack[j-1]=='{') j--;
else stack[j++]=stack[i];
i++;
}
return j==0;
}
}