有效的括号--算法练习

leetcode20.有效的括号

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

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

示例 3：

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

思路： 这道题有一规律：

1. 右括号前面，必须是相对应的左括号，才能抵消！
2. 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！

也就是说左括号我们直接放入栈中即可，发现是右括号就要对比是否跟栈顶元素相匹配，不匹配就返回false

所以先设定好map，再判定是否是左边的括号，是则进栈，不是则判定与最后一个进栈的括号是否匹配，如果匹配那么则出栈，不匹配则返回false，

最后再判断已经全部出栈，如果没有全部出栈，则也说明括号没有完全匹配

具体代码如下：

var isValid = function(s) {
    const map = { '{': '}', '(': ')', '[': ']' };
    const stack = [];
    for(let i of s){
        if(map[i]){
            stack.push(i);
        } else {
            if(map[stack[stack.length - 1]] === i){
                stack.pop()
            }else{
                return false;
            }
        }
    }
    return stack.length === 0;
};