0020._Valid_Parentheses.md

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