# 检查括号是否有效
来源: https://leetcode.cn/problems/valid-parentheses/ (opens new window)
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
解题思路:
利用栈的特性(LIFO), 构建一个 Map 括号映射, 左括号为 key , 右括号为 value, 将字符串中存在左括号压入栈中, 右括号出栈顶, 最后栈中如果有剩余长度则表示不合法.
点击查看代码
/**
* 检查括号是否有效
* @param {string} str
* @returns boolean
*
* 时间复杂度: O(n)
* 空间复杂度: O(n + |∑|). ∑ 指的是字符集, 括号数为 6, 则 ∑ = 6
*/
const isValidBrackets = (str = '') => {
if (str.length % 2 === 1) return false
// 字面量对象
// const map = {
// '{': '}',
// '[': ']',
// '(': ')'
// }
// const stack = []
// for (const char of str) {
// if (map[char]) {
// stack.push(char)
// } else {
// if (stack.length === 0 || char !== map[stack.pop()]) {
// return false
// }
// }
// }
// map
const map = new Map([
['{', '}'],
['[', ']'],
['(', ')'],
])
const stack = []
for (const char of str) {
if (map.has(char)) {
stack.push(char)
} else {
if (stack.length === 0 || char !== map.get(stack.pop())) {
return false
}
}
}
return !stack.length
// replace
// refs: https://leetcode.cn/problems/valid-parentheses/solution/by-mr-wang-y-p-uz6a/
// 有效的长度只需取一半
// const len = str.length / 2
// for (let i = 0; i < len; i++) {
// str = str.replace('{}', '')
// .replace('[]', '')
// .replace('()', '')
// }
// return str.length === 0
}
// ---------- Test ----------
const str = '{]()}[}[{])(()'
const str2 = '()[]{}'
const str3 = '(]'
console.log(isValidBrackets(str)) // false
console.log(isValidBrackets(str2)) // true
console.log(isValidBrackets(str3)) // false
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69