leetcode 20.有效括号 栈的简单应用

题目

数据结构

栈

code

var isValid = function(s) {
    // 空串和长度为奇数的字符串一定不符合要求
    if(!s || s.len%2){
        return true
    }

    let match = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    let stack = []
    let len = s.length
    
    for(let i=0; i<len; i++){
        const ch = s[i]
        if(ch==='[' || ch=='(' || ch=='{'){
            // 如果是左括号, 将与之匹配的右括号入栈
            stack.push(match[ch])
        }else{
            // 如果是右括号, 与栈进行判断
            if(!stack.length || stack.pop() !== ch){
                // 因为是括号应该是闭合的 {[()]}、{}[]()这两种是符合要求的
                // 这是不符合要求的: {([})]、{)[(]}
                // 若栈中没有元素, 则说明该有括号前面没有和它匹配的左括号
                // 若栈顶元素不与当前元素匹配, 那么说明当前的右括号没有和他成对的有效左括号
                return false
            }
        }
    }

    // 若最后栈中没有元素, 则说明所有括号均有效
    // 若还剩括号没有匹配, 那么说明存在无效括号
    return !stack.length
};
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
31
32
33
34
35