leetcode20：有效的括号

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

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

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true

提示

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

问题分析

1.  a = “()”, b="[]", c="{}"
2. 至少有一个存在字符串中即可
3. 抽象一下：
   1. a = [1, -1]
   2. b = [2, -2]
   3. c = [3, -3]
4. 直接用，str.replace，替换到最后为空字符串为止

我的实现(还有问题，效率奇低…)

var a = "()",
  b = "[]",
  c = "{}";

var isValid = function (str) {
  var len_ = str.length - 1;
  for (var i = 0; i < len_; i++) {
    var cur = str[i];
    var next = str[i + 1];
    var cn = cur + next;
    if (cn === a || cn === b || cn === c) {
      if (len_ === 1) return true;
      str = str.replace(cn, "");
      if (str === "") return true;
      return isValid(str);
    }
  }
  return false;
};

console.log(
  isValid("()"),
  isValid("()[]{}"),
  isValid("(]"),
  isValid("([)]"),
  isValid("{[]}"),
  isValid("[]}{")
);

👍 另一种思路

1. 用 replace 的办法
2. 最多替换 str.length / 2 可以将 str 变成空
3. 如果不为空，则肯定不符合条件

/**
 * @param {string} s
 * @return {boolean}
 */
var a = "()",
  b = "[]",
  c = "{}";
var emp = ""
var isValid = function (str) {
  var len_ = str.length / 2;
  for (var i = 0; i < len_; i++) {
    str = str.replace(a, emp).replace(b, emp).replace(c, emp);
  }
  return str.length === 0;
};

 

参考

https://leetcode-cn.com/problems/valid-parentheses