20-有效的括号

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

官方示例

使用for,更改for of

让进栈操作置前

var isValid = function (s) {
  const n = s.length;
  if (n % 2 === 1) {
    return false;
  }
  const pairs = new Map([
    [")", "("],
    ["]", "["],
    ["}", "{"],
  ]);
  const stk = [];
  for (let i = 0; i < n; i++) {
    let currentStr = s[i];
    if (!pairs.has(currentStr)) {
      stk.push(currentStr);
      continue;
    }
    if (!stk.length || stk[stk.length - 1] !== pairs.get(currentStr)) {
      return false;
    }
    stk.pop();
  }
  return !stk.length;
  // for (let ch of s){
  //     if (pairs.has(ch)) {
  //         if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
  //             return false;
  //         }
  //         stk.pop();
  //     }
  //     else {
  //         stk.push(ch);
  //     }
  // };
};

使用for循环

var isValid = function (s) {
  const strLength = s.length;
  if (strLength % 2 !== 0) {
    return false;
  }
  const stack = [];
  const regStr = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  for (let i = 0; i < strLength; i++) {
    let currentStr = s[i];
    if (regStr[currentStr]) {
      stack.push(currentStr);
      continue;
    }
    if (!stack.length) {
      return false;
    }
    const lastStr = stack[stack.length - 1];
    if (currentStr !== regStr[lastStr]) {
      return false;
    }
    stack.pop();
  }
  return !stack.length;
};

// for of 也可以但没for循环快
//   for (let str of s) {
//     if (regStr[str]) {
//       stack.push(str);
//       continue;
//     }
//     if (!stack.length) {
//       return false;
//     }
//     const lastStr = stack[stack.length - 1];
//     if (str !== regStr[lastStr]) {
//       return false;
//     }
//     stack.pop();
//   }

优质解答

let isValid = function (s) {
  let sl = s.length
  if (sl % 2 !== 0) return false
  let leftToRight = {
    "{": "}",
    "[": "]",
    "(": ")",
  }
  // 建立一个反向的 value -> key 映射表
  let rightToLeft = createReversedMap(leftToRight)
  // 用来匹配左右括号的栈
  let stack = []

  for (let i = 0; i < s.length; i++) {
    let bracket = s[i]
    // 左括号 放进栈中
    if (leftToRight[bracket]) {
      stack.push(bracket)
    } else {
      let needLeftBracket = rightToLeft[bracket]
      // 左右括号都不是 直接失败
      if (!needLeftBracket) {
        return false
      }

      // 栈中取出最后一个括号 如果不是需要的那个左括号 就失败
      let lastBracket = stack.pop()
      if (needLeftBracket !== lastBracket) {
        return false
      }
    }
  }

  if (stack.length) {
    return false
  }
  return true
}

function createReversedMap(map) {
  return Object.keys(map).reduce((prev, key) => {
    const value = map[key]
    prev[value] = key
    return prev
  }, {})
}