# 20. 有效的括号：暴力法和栈方法
tags:
- string
- stack
- HOT-100
# 题目链接
https://leetcode-cn.com/problems/valid-parentheses/
# 方法一：暴力法
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
while (s.length) {
let temp = s;
s = s.replace('()', '');
s = s.replace('{}', '');
s = s.replace('[]', '');
if (s == temp) {
return false;
}
}
return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
√ Accepted
- 76/76 cases passed (76 ms)
- Your runtime beats 10 % of javascript submissions
- Your memory usage beats 6.67 % of javascript submissions (36.3 MB)
- 时间复杂度：O(n)
- 空间复杂度：O(n)
# 方法二：栈方法
LeetCode 官方解题思路写得很不错，详见：https://leetcode-cn.com/problems/valid-parentheses/solution/，在这我就不赘述了。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let rightParen = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
rightParen.push(')');
} else if (s[i] === '[') {
rightParen.push(']');
} else if (s[i] === '{') {
rightParen.push('}');
} else if (s[i] !== rightParen.pop()) {
return false;
}
}
return !rightParen.length;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
√ Accepted
- 76/76 cases passed (52 ms)
- Your runtime beats 82.79 % of javascript submissions
- Your memory usage beats 51.67 % of javascript submissions (34.1 MB)
- 时间复杂度：O(n)
- 空间复杂度：O(n)
# 方法三：栈的另一种写法
与方法二类似，只是将 if...else 判断换成了 map。
var isValid = function (s) {
var map = {
"(": ")",
"[": "]",
"{": "}"
}
var leftParen = [];
for (var paren of s){
if (paren in map) leftParen.push(paren); // 为左括号时，顺序保存
else { // 为右括号时，与数组末位匹配
if(paren !== map[leftParen.pop()]) return false;
}
}
return !leftParen.length // 防止全部为左括号
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 时间复杂度：O(n)
- 空间复杂度：O(n)