[JavaScript] LeetCode 20. Valid Parentheses

題目概要

給定一個字串 s 僅包含字符 ‘(‘、’)’、'{‘、’}’、'[‘、’]’,當連著的兩個為一組括號,就稱之為有效擴號,試著判斷字串 s 中所有括號是否皆為有效擴號,返回 boolean 結果。

輸入字符串在以下情況下有效:

  1. 起始括號必須用相同類型的括號閉合。
  2. 起始開括號必須以正確的順序閉合。
Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

解題技巧

  • 用棧的概念去解,將字串分為一個一個字符然後 push 進 array 中,再依照棧的概念,從最後兩個字符開始比較是否為相同類型的開合括號,如果是,就將最後兩個字符 pop,最後判斷 stack 的長度是否為 0 即是答案。
  • 也可以用 includes & replace 的方式來解。

程式碼

棧(Stack)解法

var isValid = function(s) {
    const stack = [];
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    
    for(let i = 0; i < s.length; i++) {
        const char = s[i];
        stack.push(char);
        
        if (stack.length < 2) continue;
        
        const lastOne = stack[stack.length - 1];
        const lastTwo = stack[stack.length - 2];
        
        if (map[lastOne] === lastTwo) {
            stack.pop();
            stack.pop();
        }
    }
    
    return stack.length === 0;
};
image 9 [JavaScript] LeetCode 20. Valid Parentheses

正則解法

var isValid = function (s) {
  while (s.includes("[]") || s.includes("()") || s.includes("{}")) {
    s = s.replace("[]", "").replace("()", "").replace("{}", "");
  }

  return s.length === 0;
};
image 11 [JavaScript] LeetCode 20. Valid Parentheses
0 0 評分數
Article Rating
訂閱
通知
guest

0 Comments
在線反饋
查看所有評論