20. Valid Parentheses

Tags

1. Stack
2. String

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

题意：

给定一个字符串包含'(', ')', '{', '}', '[' 和 ']',这几个字符，判断输入的字符串是否有效。括号必须以正确的顺序关闭。

分析：

根据题目的描述，我们知道这是一个判断输入的字符串是否与目标值匹配且是否按照对称规则顺序排列的。因此我们可以提取出几个关键点来：

1. 需要匹配目标字符串。->也就是说需要自己构建被匹配的一个目标值
2. 必须按照对称规则匹配。->需要有一一对应的逻辑关系，方便查询比对

思路：

根据分析，发现最好存储被匹配目标字符串就是ES6的Map结构，当然也可以使用ES5对象模拟Map结构，做到满足刚刚我们分析时的两点要求。最终总体思路如下：

1. 新建一个数组来临时存储能比对上Map中key的字符；
2. 如果Map中的key与目标字符比配存入数组；
3. 如果Map中的value值与目标字符相等。则key数组不为空，且最后一个key所对应的value值与目标字符相等，则将数组中的该key删除，否则返回false；
4. 最终如果数组中的key值为0就返回true，不为0就返回false。

复杂度：

循环一次，所以时间复杂度为O(n²)

Js实现：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let map = new Map();
    map.set('(', ')');
    map.set('[', ']');
    map.set('{', '}');
    let stack = [];
    for (let i = 0; i < s.length; i++) {
        let curr = s.charAt(i);
        for(let key of map.keys()){
          if (key==curr) {
            stack.push(curr);
          }  else if(map.get(key) == curr){
              if (stack!=[] && map.get(stack[stack.length-1]) == curr) {
                    stack.pop();
                } else {
                    return false;
                }
          }  
        }
    }

    return !stack.length;
};