力扣
我的力扣题解
一如既往地，思考了 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;
}
};
|
清风迅来