DOJO004

Dashool 創辦人
喜歡調酒
Rails、Nextjs、TypeScript

來刷 LeetCode 吧! 11 20.Valid Parentheses

LeetCode

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

題目分析

給一個字串 “s”，要找出是否為對稱的括號。

括號的類型 “()”、”[]”、”{}”。

要檢查開括號、閉括號的順序是否正確。

第一直覺

檢查的過程類似於 JavaScript 的堆疊佇列。

var isValid = function (s) {
  const stack = [];
  const map = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (let i = 0; i < s.length; i++) {
  // 若 s[i] 為開括號，將對應的閉括號放入 stack。
  // 若 s[i] 為閉括號，將 stack 最後一個取出，看是否相等。
    if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
      stack.push(map[s[i]]);
    } else {
      if (stack.pop() !== s[i]) return false;
    }
  }
  // 都檢查完畢，查看 stack 是否為空。
  return stack.length === 0;
};

console.log(isValid("()")); //true
console.log(isValid("()[]{}")); // true
console.log(isValid("([)]")); //false
console.log(isValid("(]")); //false

優化寫法

可以將 for 迴圈寫得更簡潔一點，增加可讀性。

var isValid = function (s) {
  const stack = [];
  const map = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (let char of s) {
    if (char in map) {
      stack.push(map[char]);
    } else if (stack.length === 0 || stack.pop() !== char) {
      return false;
    }
  }

  return stack.length === 0;
};

console.log(isValid("()")); //true
console.log(isValid("()[]{}")); // true
console.log(isValid("([)]")); //false
console.log(isValid("(]")); //false