数组索引版本
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串
* @return bool布尔型
*/
export function isValid(s: string): boolean {
// write code here
// 要求:空间复杂度 O(n),时间复杂度 O(n)
const tpl = ['[',']','{','}','(',')']
const len = s.length
// 奇数长度肯定不闭合
if(len % 2){return false}
// 第一个是不能是偶数
if((tpl.indexOf(s[0]) + 1) % 2 === 0){
return false
}
// 左边栈,先把第一个入栈
const leftArr: string[] = [s[0]]
// 从第二个开始
for(let i = 1; i < len; i++){
const tplIdx = tpl.indexOf(s[i])
if(tplIdx < 0){
return false
}
// 奇数, 左边
if((tplIdx + 1) % 2){
// 把自己推入栈
leftArr.push(tpl[tplIdx])
}else{
// 遇到右边,需要出栈判断是不是匹配另一半, 不匹配的直接验证失败
if(tpl[tplIdx - 1] !== leftArr.pop()){
return false
}
}
}
return !leftArr.length
}