题一：有效的括号

题目地址：https://leetcode-cn.com/problems/valid-parentheses/，题号：20
image.png
【解题思路】

  • 使用栈的方法：
  1. 对于左括号，首先肯定是合法的，只是后续需要判断是否有匹配闭合的有括号，先push到栈中；
  2. 右括号是不能独立存在的，如果一上来就是右括号，那肯定是不合法的；那么右括号首先要匹配到栈顶的第一个元素是否与它相匹配，如果匹配，那么就需要把栈顶元素给pop出去；如果不匹配直接返回false；
  3. 当走完整个流程之后，还需要判断栈必须为空的；
    1. var isValid = function(s) {
    2.  var stack = [];
    3.  var map = new Map();
    4.  map.set("}", "{");
    5.  map.set("]", "[");
    6.  map.set(")", "(");
    7.  for(let value of s) {
    8.      if(value && !map.has(value)) {    // 如果是左括号就入栈
    9.          stack.unshift(value);
    10.      } else if(stack.length === 0 && map.has(value)) {        // 排除"["
    11.        return false;
    12.      } else if(stack.length > 0 && stack.shift() !== map.get(value)) {    // 排除掉不匹配的情况
    13.        return false;
    14.      }
    15.  }
    16.  if(stack.length>0) return false;    // 确保最后stack为空
    17.  return true;
    18. };
    这个方法中，由于每个字符串都有且只能进入一次栈中，它的时间复杂度是O(n)，空间复杂度也是O(n)。

另一个解法如下。

  1. var isValid = function(s) {
  2.     var length;
  3.     do {
  4.         length = s.length;
  5.         s = s.replace("{}","").replace("[]","").replace("()","");
  6.     } while(length != s.length);
  7.     return s.length == 0;
  8. };

在这个方法中，首先代码简洁性也是比较高的，然后思路是通过不断地抵消左右匹配括号，直到最后字符串为空。但是时间复杂度在平均情况下是达到了 O(1/2n)，也就是O(n)，所以还是推荐第一种方法。

to be continue…