＊javascript solution
[easy] 20. 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

Constraints:

• 1 <= s.length <= 10⁴
• s consists of parentheses only '()[]{}'.

題意：
給一個字串，只能由 '()'、'{}'、'[]' 組成，檢查字串組成是否正確。

 
我的思路是跑一次字串，然後用一個陣列儲存 '()'、'{}'、'[]'，如果有符合就以 '' 取代，字串最後若為空則是合法字串。

這邊要用另外的字串來做取代，不然迴圈會有問題。
 

var isValid = function(s) {
  let tmp = s
  let ans = ['()', '{}', '[]']
  for (let i = 0; i < s.length; i++) {
    ans.forEach(item => {
      tmp = tmp.replace(item,'')
    })
  }
  return tmp.length > 0 ? false : true
};

result:

可以是可以，不過效能不好，來問一下 google 大神了。

 
下面這個解法的思路是：
用 pop() 方法（取出陣列最後一個元素）來完成 stack 先進後出的特性，
左括號放入 stack，右括號與 match 物件比對最後一個 stack 是否與左括號對應。
 
合法的字串，右括號應和最後一個 stack 相對應。
 

var isValid = function(s) {
  let stack = []
  
  let left = ['(','[','{'];
  let right = [')',']','}'];
  let match = {
    ')':'(',
    ']':'[',
    '}':'{'
  }
  
  for (let i = 0; i < s.length; i++) {
    // s[i] 為左括號，放入 stack
    if (left.indexOf(s[i]) > -1) {
      stack.push(s[i])
    }
    else { // s[i] 為右括號的狀況
      let stackStr = stack.pop() // 從最後一個左括號開始配對
      if (match[s[i]] !== stackStr) {
        return false
      }
    }
  }
   
  // 字串不為空，且組成正確，則迴圈結束時 stack 應為 0
  return s.length > 0 && stack.length === 0
};

result:

參考資料
LeetCode 20. Valid Parentheses