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;
};