> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/stack/20-valid-parentheses.md).

# # 20 Valid Parentheses (有圖)

[LeetCode](https://leetcode.com/problems/valid-parentheses/)

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
```

```
Example 1:

Input: "()"
Output: true
Example 2:

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

/**
 * @param {string} str
 * @return {boolean}
 */
var isValid = function(str) {}
```

### Edge Case

* 中間可能有除了 ( ) { } \[ ] ，其他的符號或字母
* 空值

```
/**
 * Additional examples and edge cases:
 */
console.log( isValid("") ); // true
console.log( isValid("]") ); // false
console.log( isValid("{{[[(())]]}}") ); // true
console.log( isValid("[]{()()[[{}]]}") ); // true
console.log( isValid("a b [d] { (g) (h) i [-[ {;} ]-] }") ); // true
```

### 怎麼解

需要了解 Stack 觀念

* 遇到 { \[ ( 就放到 stack 裡

![](/files/-LqtSP36q_9U13ZorIf9)

* 遇到 ) ] } 就去抓 stack 看有沒有相對應的 ( \[ {
  * 若沒有就回傳 false
  * 若有就繼續檢查下一個

![](/files/-LqtSYa_npzgRdWGg5ID)

```
function isBalanced(str){
  let current, myStack = [];
  for(let i=0; i<str.length; i++){
    // 把 split 拿掉 string 本身就有 length 的屬性
    current = str[i]
    
    if(current === '{' || current === '[' || current === '('){
      // 直接用 array 原生 push 更簡潔
      myStack.push(current)
    }else if(current === '}'){
      // 就得判斷兩次重覆 所以拿掉剩判斷一次就好
      // pop 回傳移掉那個值, 然後會把 stack 最後面移掉
      return myStack.pop() !== '{';
    }else if(current === ']'){
      return myStack.pop() !== '[';
    }else if(current === ')'){
      return myStack.pop() !== '(';
    }
  }
   return myStack.length === 0;  // [""] true
}
// Runtime faster than 82.86%
```

### 學到什麼

需要對資料結構跟語言本身相當了解才行 (例如，我若不知道 array.pop() 回傳的是被移掉那個值，我可能需要多好幾行程式碼去處理，處裡時同時又讓程式效能更差了 )