数据结构与算法之字符串: Leetcode 20. 有效的括号 (Typescript版)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法之字符串: Leetcode 20. 有效的括号 (Typescript版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有效的括号

https://leetcode.cn/problems/valid-parentheses/

描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

1 <= s.length <= $10^4$
s 仅由括号 ‘()[]{}’ 组成

算法实现

1 ）方案 1

function isValid(s: string): boolean {
    // 奇数直接不合法
    if (s.length % 2 === 1) {
        return false;
    }
    const stack = [];
    const leftArr = ['(', '{', '[']
    for(let i = 0; i < s.length; i ++) {
        // 拿出当前字符
        const c = s[i];
        // 是左括号进栈
        if(leftArr.includes(c)) {
            stack.push(c);
        } else {
            // else 是右括号的情况，拿出栈顶元素(数组最后一位)
            const t = stack[stack.length - 1];
            // 对比栈顶元素和当前元素是否匹配
            const isMatch = (t === '(' && c === ')') || (t === '{' && c === '}') || (t === '[' && c === ']')
            if(isMatch) {
                // 将栈顶元素出栈
                stack.pop();
            } else {
                // 不匹配，直接退出
                return false;
            }
        }
    }
    // 字符串扫描完成, 栈应该为空，不为空则false
    return stack.length === 0; 
};

解题思路
- 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前, 如 {[]}
- 满足后进先出，可考虑用栈
- 新建一个栈
- 扫描字符串，遇左括号入栈，遇和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法
- 字符串扫描完了，栈是空的就合法，否则不合法

2 ）方案 2文章来源地址https://www.toymoban.com/news/detail-429188.html

function isValid(s: string): boolean {
    // 奇数直接不合法
    if (s.length % 2 === 1) {
        return false;
    }
    const stack = [];
    // 用字典存储 这种方式缺点是空间复杂度较高
    const map = new Map([
        ['(', ')'],
        ['{', '}'],
        ['[', ']']
    ])
    /*
    // 这种方式是写起来繁琐
    const map = new Map()
    map.set('(', ')');
    map.set('{', '}');
    map.set('[', ']');
    */
    for(let i = 0; i < s.length; i++) {
        // 拿出当前字符
        const c = s[i];
        // 是左括号进栈
        if(map.has(c)) {
            stack.push(c);
        } else {
            // else 是右括号的情况
            // 拿出栈顶元素(数组最后一位)
            const t = stack[stack.length - 1];
            // 对比栈顶元素和当前元素是否匹配
            // 左括号===当前元素
            if(map.get(t) === c) {
                // 将栈顶元素出栈
                stack.pop();
            } else {
                return false;
            }
        }
    }
    // 字符串扫描完成, 栈应该为空，不为空则false
    return stack.length === 0; 
}