20 有效的括号
/// 97.08% 68.03%
var isValid = function(s) {
let stack = [];
for(i of s){
if (i === '(' || i === '{' || i === '['){
stack.push(i)
}else{
if (stack.length > 0){
let top = stack.pop()
if (!top) return false
if ((top === '(' && i === ')') || (top === '[' && i === ']') || (top === '{' && i === '}')){
}else{
return false
}
}else{
return false
}
}
}
return stack.length === 0
};
因为每个元素都会且仅会进入栈一次，每次时间复杂度是O(1)，因此总的时间复杂度是O(n)。空间复杂度也是O(n)。还有一个结果让人疑惑的解法。
/// 99.85% 63.52%
var isValid = function(s) {
let stack = [];
let m = new Map()
m.set(')', '(')
m.set(']', '[')
m.set('}', '{')
for(i of s){
if (!m.has(i)){
stack.push(i)
}else{
if (stack.length > 0 && stack.pop() === m.get(i)){
}else{
return false
}
}
}
return stack.length === 0
};
这个让我疑惑的地方在于多使用了一个Map而且主要改动的代码也只是括号的配对的那个if语句，居然速度快了足足8ms。