0020._Valid_Parentheses

发表于 分类于 ， ，

020. Valid Parentheses

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
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:

1
2
Input: "()"
Output: true

Example 2:

1
2
Input: "()[]{}"
Output: true

Example 3:

1
2
Input: "(]"
Output: false

Example 4:

1
2
Input: "([)]"
Output: false

Example 5:

1
2
Input: "{[]}"
Output: true

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @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
    };