20md.md

LeetCode 20. Valid Parentheses

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

##翻譯 給一個只包含'(', ')', '{', '}', '[' , ']'這些括號字元的字串，判斷這些括號是不是合法的。 右括號必須依照正確的順序出現，"()" 與 "()[]{}" 都是合法的，但"(]" 和 "([)]"就不是。

##思路 用stack先進後出的特性來解，遇到左括號就放入stack，遇到右括號就取出stack裡面的左括號比對是否合法。

例如說字串 " ( [ ) ] " ，  '(' 左括號，放入stack -> stack='(', '['放入stack = '(['  
')'右括號，取出stack -> '[' ，  [)是一個不match的組合，就回傳false  

##解題

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if(!s) return true;
    
    // 使用stack還儲存左括號
    var stack = [];
    
    var left = ['(','[','{'];
    var right = [')',']','}'];
    var match = {
        ')':'(',
        ']':'[',
        '}':'{'
    }
    
    for(var i in s){
        // 左括號，放入stack
        if(left.indexOf(s[i]) > -1){
            stack.push(s[i]);  
        } 
        
        // 右括號，從stack取出左括號判斷是否match
        if(right.indexOf(s[i]) > -1){
            var stackStr = stack.pop();  
            if(match[s[i]] != stackStr) {
                return false;
            }
        } 
    }
    
    // 如果左右括號都match的話，stack應該為空
    return stack.length == 0;
};