20. 有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/

代码

function isValid(s: string): boolean {
    const arr = new Array();
    for(let i = 0; i < s.length; i++){
        const cur = s[i];
        if(cur === ')' || cur === ']' || cur === '}'){
            const left = arr.pop();
            if((left === '(' && cur === ')') ||
            (left === '[' && cur === ']') || 
            (left === '{' && cur === '}')){
                continue;
            } else return false;
        }
        else{
            arr.push(s[i])
        }
    }
    if(arr.length !== 0) return false;
    return true;
};

function isValid2(s: string): boolean {
    const arr = new Array()
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    for(const char of s){
        if(map[char]){
            const left = arr.pop();
            if(left !== map[char]) return false;
        } else arr.push(char);
    }
    if(arr.length !== 0) return false;
    return true;
}

思路

这份代码使用了栈来匹配括号，并给出了两种写法。

方法一：直接分类判断

1. 遍历字符串中的每个字符
2. 如果当前字符是左括号，就压入栈中
3. 如果当前字符是右括号，就弹出栈顶元素进行匹配
4. 只要出现不匹配的情况，立即返回 false
5. 遍历结束后，如果栈为空，说明所有括号都正确匹配

方法二：映射表优化

1. 用对象 map 维护右括号到左括号的对应关系
2. 遇到右括号时，直接判断栈顶是否等于它对应的左括号
3. 如果不相等，返回 false
4. 否则继续遍历，最后再检查栈是否为空

关键点

• 栈天然适合处理“最近的左括号和当前右括号匹配”的问题

• 遇到右括号时，必须和栈顶最近的左括号匹配

• 遍历结束后栈必须为空，否则说明还有未闭合的左括号

• 时间复杂度 $O(n)$，其中 $n$ 是字符串长度

• 空间复杂度 $O(n)$，最坏情况下栈中会存储所有左括号