题解 | #有效括号序列#

栈 + 词典对象

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param s string字符串 
 * @return bool布尔型
 */
export function isValid(s: string): boolean {
    // write code here
    // 要求：空间复杂度 O(n)，时间复杂度 O(n)
    const tokenDict = {
        '[':']',
        '{':'}',
        '(':')'
    }
    const len = s.length

    // 奇数长度肯定不闭合
    if(len % 2){return false}
    // 第一个不是左边
    if(!tokenDict[s[0]]){
        return false
    }
    
    // 右边待出栈
    const rightArr: string[] = []

    for(let i = 0; i < len; i++){
        // 尝试查找对应的右边
        const rightKey = tokenDict[s[i]]
       
        if(rightKey){
            // 把右边推入栈，等待一个右边
            rightArr.push(rightKey)
        }else{
            // 当s[i]为右边，出栈，并查看栈顶是不是一样
            if(s[i] !== rightArr.pop()){
              return false
            }
        }

    }
    
    
    return !rightArr.length
}