020. Valid Parentheses
难度: Easy
刷题内容
原题连接
- https://leetcode.com/problems/two-sum
内容描述
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
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
解题方案
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(N)***
代码：
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if(!s){
return true;
}
let array = [];
for(let i = 0,len = s.length; i<len; i++){
let cur = s.charAt(i);
if(cur === '(' || cur === '{' || cur === '['){
array.push(cur);
}else if(!array.length){
return false;
}else{
let pre = array.pop();
if(pre === '(' && cur !== ')'){
return false;
}
if(pre === '{' && cur !== '}'){
return false;
}
if(pre === '[' && cur !== ']'){
return false;
}
}
}
return !array.length
};
