# 20. Valid Parentheses

## 題目概要

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

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

* 起始括號必須用相同類型的括號閉合。
* 起始開括號必須以正確的順序閉合。

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

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

## 程式碼

### 棧(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;
};


### 正則解法

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

  return s.length === 0;
};