问题思路
将所有的左半边括号push到栈内,然后遇到右半边括号,就将其与栈顶元素匹配测试,若能匹配成功则继续匹配,反之输出false。
在这之间注意比较当栈内没有元素了,而字符串还有待匹配的字符,输出false,当栈内还有元素,外面与之匹配测试的右半边括号,也输出false。
ts实现
function isValid(s: string): boolean {
let stack: Array<string> = []
for (let i of s) {
if (['(', '[', '{'].includes(i)) {
stack.push(i)
} else {
switch (i) {
case ')':
if (stack[stack.length - 1] === '(') {
stack.pop()
} else {
return false
}
break
case ']':
if (stack[stack.length - 1] === '[') {
stack.pop()
} else {
return false
}
break
case '}':
if (stack[stack.length - 1] === '{') {
stack.pop()
} else {
return false
}
break
}
}
}
return stack.length ? false : true
}
之前的java代码实现
栈实现
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 {
private static HashMap<Character, Character> map = new HashMap<>();
static {
// key - value
map.put('(', ')');
map.put('{', '}');
map.put('[', ']');
}
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 (map.containsKey(c)) { // 左括号
stack.push(c);
} else { // 右括号
if (stack.isEmpty()) return false;
if (c != map.get(stack.pop())) return false;
}
}
return stack.isEmpty();
}
}
评论区