【LeetCode-简单】20.有效的括号

By yesmore on 2021-09-06
阅读时间 3 分钟
文章共 647
阅读量

要点:有效的括号、栈

描述

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
给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

思路

使用栈,遍历输入字符串

如果当前字符为左半边括号时,则将其压入栈中

如果遇到右半边括号时,分类讨论:

1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环

2)若此时栈为空,则直接返回 false

3)若不为对应的左半边括号,反之返回 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
/**
* @param {string} s
* @return {boolean}
*/
const isValid = function(s) {
const stack = []
for (let i = 0; i < s.length; i++) {
const c = s[i]
switch (c) {
case '(':
stack.push(')')
break
case '{':
stack.push('}')
break
case '[':
stack.push(']')
break
default:
if (c !== stack.pop()) {
return false;
}
}

}
return stack.length === 0;
};
  • 91/91 cases passed (68 ms)
  • Your runtime beats 87.56 % of javascript submissions
  • Your memory usage beats 97.17 % of javascript submissions (37.6 MB)

时间复杂度:$O(N)$

空间复杂度:$O(N)$

方法二

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
var isValid = function(s) {
const stack = [],
map = {
"(":")",
"{":"}",
"[":"]"
};
for(const x of s) {
if(x in map) {
stack.push(x);
console.log('入栈:'+x)
continue;
};
console.log('出栈:'+x)
if(map[stack.pop()] !== x) return false;
}
return !stack.length;
};

// 测试
console.log(isValid('({})'))

// 测试结果:
入栈:(
入栈:{
出栈:}
出栈:)
true
  • 91/91 cases passed (60 ms)
  • Your runtime beats 98.53 % of javascript submissions
  • Your memory usage beats 60.39 % of javascript submissions (38.2 MB)

时间复杂度:$O(N)$

空间复杂度:$O(N)$

方法三

正则解析

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
while (s.includes("[]") || s.includes("()") || s.includes("{}")) {
s = s.replace("[]", "").replace("()", "").replace("{}", "");
}
s = s.replace("[]", "").replace("()", "").replace("{}", "");
return s.length === 0;
};
  • 91/91 cases passed (116 ms)
  • Your runtime beats 6.64 % of javascript submissions
  • Your memory usage beats 5.19 % of javascript submissions (43.3 MB)

时间复杂度:取决于正则引擎的实现

空间复杂度:取决于正则引擎的实现


Tips: Please indicate the source and original author when reprinting or quoting this article.