# 20 Valid Parentheses (有圖)

Stack 就像疊盤子，先進後出

LeetCode

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 裡

• 遇到 ) ] } 就去抓 stack 看有沒有相對應的 ( [ {

  • 若沒有就回傳 false

  • 若有就繼續檢查下一個

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() 回傳的是被移掉那個值，我可能需要多好幾行程式碼去處理，處裡時同時又讓程式效能更差了 )