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

有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1

输入: “()” 输出: true

解题思路

利用栈来解决。

思路一： 栈

解决一

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isValid = function(s) {
  6.     if(s.length%2!== 0){
  7.         return false;
  8.     }
  9.     let stack = [];
  10.     let left = '({[';
  11.     for(var i = 0; i< s.length;i++){
  12.         if(left.includes(s[i])){
  13.             stack.push(s[i]);
  14.         }else{
  15.             let popS = stack.pop();
  16.             if(!(((s[i] === '}' && popS === '{') || (s[i] === ')' && popS === '(')) || (s[i]===']' && popS === '['))){
  17.                 return false;
  18.             }
  19.         }
  20.     }
  21.     if(stack.length !== 0){
  22.         return false;
  23.     }
  24.     return true;
  25. };

解法二

// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
  "(": ")",
  "[": "]",
  "{": "}"
};

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
  // 结合题意，空字符串无条件判断为 true
  if (!s) {
    return true;
  }
  // 初始化 stack 数组
  const stack = [];
  // 缓存字符串长度
  const len = s.length;
  // 遍历字符串
  for (let i = 0; i < len; i++) {
    // 缓存单个字符
    const ch = s[i];
    // 判断是否是左括号，这里我为了实现加速，没有用数组的 includes 方法，直接手写判断逻辑
    if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);
    // 若不是左括号，则必须是和栈顶的左括号相配对的右括号
    else {
      // 若栈不为空，且栈顶的左括号没有和当前字符匹配上，那么判为无效
      if (!stack.length || stack.pop() !== ch) {
        return false;
      }
    }
  }
  // 若所有的括号都能配对成功，那么最后栈应该是空的
  return !stack.length;
};

思路二：replace替代法

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(s.length%2!== 0){
        return false;
    }
    let t = s.length/2;
    while(t>0){
        s=s.replace("()","");
        s=s.replace("{}", "");
        s=s.replace("[]","");
        t--;
    }
    return s.length === 0;
};