目录

20. 有效的括号(简单)

力扣

我的力扣题解

一如既往地,思考了 5 分钟只有暴力解法,于是果断去参考了一下官方题解

题目描述

定义:任意左括号的右边,要么也是左括号,要么是与之成对的右括号。

解题思路

ps:某种意义上,这题的解题思路相当于是一维的连连看游戏,不断地消除相邻的成对左右括号,如果最后全部消除,就是有效的括号,反之无效。

遍历字符

  • 遇到左括号依次记录下来
  • 遇到右括号时尝试“连连看”来匹配对应的左括号
    • 匹配成功,则成功消除这对括号
    • 匹配失败,游戏结束

所以恰好可以利用的特性:

  • 只有 2 种操作,入栈出栈,分别对应左括号入栈(记录)右括号出栈(匹配-消除)
  • 先入后出:保证了有序入栈,每次出栈操作的都是最新入栈的值

优化点

  • 初始化剪枝,字符串奇数时,返回 false
  • 遍历中剪枝,如果栈中待匹配字符数超过一半,返回 false (本身也有计算,也许可能大概是负优化?)

v 1.0.0

2020年08月14日

统计

版本 耗时 超越 内存 超越 更新时间
1.0.0 76 ms 59.07% 37.6 MB 88.49% 2020年08月14日12:30:00

代码

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const len = s.length;
    /**
     * 特殊情况处理
     */

    // 空字符串可被认为是有效字符串
    if(len === 0) {
        return true;
    }

    // 剪枝,字符串长度为奇数,必然无效
    if(len % 2 === 1) {
        return false;
    }

    // 定义字符串匹配 map
    const map = {
        '}' : '{',
        ')' : '(',
        ']' : '['
    }
    // 使用栈来校验闭合情况
    const stack = []
    for (let i = 0; i <= len - 1; i++) {
        if(!map[s[i]]) {
            // 左括号,入栈
            stack.push(s[i]);
        } else {
            // 右括号,出栈,判断如果与前一个括号不匹配,返回 false
            if(map[s[i]] !== stack.pop()) {
                return false;
            } 
        }
        // 剪枝,如果待匹配左括号的数量超过一半,返回 false (奇数先前已排除)
        if(stack.length > len / 2) {
            return false;
        }
    }

    // 遍历结束,如果仍有未匹配完的左括号,返回 false
    if(stack.length > 0) {
        return false;
    } else {
        return true;
    }

};