# 20. Valid Parentheses

### Leetcode

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

### 題目

Given a string `s` containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

**Example 1:**

```
Input: s = "()"
Output: true
```

**Example 2:**

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

**Example 3:**

```
Input: s = "(]"
Output: false
```

**Example 4:**

```
Input: s = "([)]"
Output: false
```

**Example 5:**

```
Input: s = "{[]}"
Output: true
```

### 分析 <a href="#ti-jie" id="ti-jie"></a>

感覺這一題的描述不太完整，不能確定哪種排列算是 valid 的

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - Stack**

用後進先出的 Stack 來存放 open 的括號，然後在遍歷的過程中，如果遇到 close 的括號就跟 Stack 最上層 open 的括號比對看是不是可以配對成同一組，那如果遇到的是 open 的括號就再把他加入到 Stack 裡

```javascript
var isValid = function(s) {
    const stack = [s[0]];
    const mapEndToStartBracket = {
        ")": "(",
        "}": "{",
        "]": "["
    }
    
    for(let i=1; i<s.length; i++) {
        const char = s[i];
        const start = mapEndToStartBracket[char];
        // char 是 ) or } or ]
        if(start) {
            if(stack.pop() !== start) return false;
        } else {
            stack.push(char);
        }
    }
    
    return !stack.length;
};
```

Runtime: 76 ms, faster than 68.47% of JavaScript online submissions for Valid Parentheses.

Memory Usage: 38.9 MB, less than 74.18% of JavaScript online submissions for Valid Parentheses.

### 測資

```javascript
let s = "()[]{}"; // true
s = "([)]"; // false
s = "{[]}"; // true

console.log(isValid(s))
```
