20.有效的括号

题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

示例1：
输入：s = "()"
输出：true

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

示例3：
输入：s = "(]"
输出：false

示例4：
输入：s = "([)]"
输出：false

示例5：
输入：s = "{[]}"
输出：true

提示：

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

进阶：你能不将整数转为字符串来解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses

思路：

• 用到了栈的思想

代码：

var isValid = function(s) {
    let i,j=0,len=s.length,arr=new Array();
    for(i=0;i<len;i++){
        if(Map[s[i]]>=1&&Map[s[i]]<=3){
            arr[j++]=Map[s[i]];
        }else if(arr.length!=0&&Map[s[i]]==(arr[arr.length-1]+3)){
            arr.pop();//删除数组的最后一个元素
            j--;
        }else{
            return false;
        }
    }
    if(arr.length == 0)
        return true;
    else
        return false;
};
const Map = {
    '(':1,
    '[':2,
    '{':3,
    ')':4,
    ']':5,
    '}':6
}

执行结果：

image.png

改进解法：
思路：

• 优化了映射对象

代码：

var isValid = function(s) {
    const stack = [],
          map = {
            "(":")",
            "{":"}",
            "[":"]"
          }
    for(const i of s){
        if(i in map){
            stack.push(i);
        }else if(i!=map[stack.pop()]){
            return false;
        }
    }
    return !stack.length;
};

执行结果：

image.png