题解 | #有效括号序列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param s string字符串 
 * @return bool布尔型
 */

/**
 * 解法一：栈
 * 思路：
 *（1）左括号，压栈
 *（2）右括号，则判断栈顶是否匹配（是否出栈）否则直接 return false
 * (3) 最后 return stack.length === 0
 * 时间复杂度：O(n)，其中 n 为字符串长度
 * 空间复杂度：O(n)，最坏情况下栈空间记录整个字符串长度的右括号
 */
function isMatch(left: string, right: string): boolean {
    if ((left === '{' && right === '}') 
    || (left === '[' && right === ']') 
    || (left === '(' && right === ')')) return true

    return false
}
export function isValid(s: string): boolean {
    const len = s.length
    if (len === 0) return true

    const stack = []
    const leftSymbols = '{[('
    const rightSymbols = ')]}'

    for (let i = 0; i < len; i++) {
        const char = s[i]

        if (leftSymbols.includes(char)) {
            // 左括号，压栈
            stack.push(char)
        } else if (rightSymbols.includes(char)) {
            // 右括号，判断栈顶（是否出栈）
            const top = stack[stack.length - 1]

            if (isMatch(top, char)) {
                stack.pop()
            } else {
                return false
            }
        }
    }

    return stack.length === 0
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview