leetcode 刷题记：20. 有效的括号

这道题其实在编辑器和编译器上使用还是比较广的。

问题描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

// @algorithm @lc id=20 lang=javascript 
// @title valid-parentheses
// @test("()")=true
// @test("()[]{}")=true
// @test("(]")=false
// @test("([)]")=false
// @test("{[]}")=true
/**

解题思路

用一个map来存储括号的闭合关系，用一个数组来当栈用。所有左括号都把对应的右括号入栈，遇到右括号都需要出栈，并对比。如果不能形成匹配关系则说明括号不匹配。如果结束遍历后栈里还存在元素，也被视为括号不匹配。

代码：

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
    const map = {
        "[": "]", "(": ")", "{": "}"
    };
    const stack = [];
    for (let index = 0; index < s.length; index++) {
        if (map[s[index]]) {
            stack.push(s[index]);
        } else {
            if (map[stack.pop()] !== s[index]) return false;
        }
    }
    return stack.length === 0;
};