423. 有效的括号序列

Posted on

Description

给定一个字符串所表示的括号序列，包含以下字符： ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’， 判定是否是有效的括号序列。

Example

括号必须依照 “()” 顺序表示， “()[]{}” 是有效的括号，但 “([)]”则是无效的括号。
O(n)的时间，n为括号的个数

Solution

这类题目也不用多想，用栈。两个栈比较。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
/**
 * @param s: A string
 * @return: whether the string is a valid parentheses
 */
const isValidParentheses = function (s) {
    let stack = s.split("");
    if (stack.length % 2 !==0)return false;
    let dic = {
        ')':'(',
        '}':'{',
        ']':'[',
    }
    
    let outstack = [];
    while(stack.length > 0){
        let now = stack.pop();
        if (dic[now]){
            outstack.push(now);
        }else{
            let check = outstack.pop();
            if (dic[check] !== now)return false;
        }
    }
    return outstack.length>0?false:true;
}