问题思路

将所有的左半边括号 push 到栈内,然后遇到右半边括号,就将其与栈顶元素匹配测试,若能匹配成功则继续匹配,反之输出 false。

在这之间注意比较当栈内没有元素了,而字符串还有待匹配的字符,输出 false,当栈内还有元素,外面与之匹配测试的右半边括号,也输出 false。

代码实现

栈实现

class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();

int len = s.length();
for (int i=0;i<len;i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char left = stack.pop();
if (left == '(' && c !=')') return false;
if (left == '[' && c !=']') return false;
if (left == '{' && c !='}') return false;
}
}
return stack.isEmpty();
}
}
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i< s.length();i++){
if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}'){
return false;
}
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
stack.push(s.charAt(i));
}
if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'){
if (s.charAt(i) == ')'){
if (stack.isEmpty() == true) {
return false;
}
if (stack.pop() != '(')
return false;

}
if (s.charAt(i) == ']'){
if (stack.isEmpty() == true) {
return false;
}
if (stack.pop() != '[')
return false;

}
if (s.charAt(i) == '}'){
if (stack.isEmpty() == true) {
return false;
}
if (stack.pop() != '{')
return false;

}
}
}
if (stack.isEmpty() == true){
return true;
} else {
return false;
}

}
}

HashMap 实现

class Solution {
trueprivate static HashMap<Character, Character> map = new HashMap<>();
truestatic {
truetrue// key - value
truetruemap.put('(', ')');
truetruemap.put('{', '}');
truetruemap.put('[', ']');
true}

truepublic boolean isValid(String s) {
truetrueStack<Character> stack = new Stack<>();

truetrueint len = s.length();
truetruefor (int i = 0; i < len; i++) {
truetruetruechar c = s.charAt(i);
truetruetrueif (map.containsKey(c)) { // 左括号
truetruetruetruestack.push(c);
truetruetrue} else { // 右括号
truetruetruetrueif (stack.isEmpty()) return false;

truetruetruetrueif (c != map.get(stack.pop())) return false;
truetruetrue}
truetrue}
truetruereturn stack.isEmpty();
}
}