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