有效括号
前端小菜-贺俊兰 2020-08-27 LeetCode
# 介绍
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例1
输入: "()"
输出: true
1
2
2
示例2
输入: "()[]{}"
输出: true
1
2
2
示例3
输入: "(]"
输出: false
1
2
2
示例4
输入: "([)]"
输出: false
1
2
2
示例5
输入: "{[]}"
输出: true
1
2
2
# 题解
# 思路
判断括号的有效性可以使用「栈」这一数据结构来解决。
我们对给定的字符串 str 进行遍历,当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。
当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 str 无效,返回 false。
在遍历结束后,如果栈中没有括号,说明我们将字符串 str 中的所有括号闭合,返回 true,否则返回 false。
注意:空字符串可被认为是有效字符串。
注意:如果字符串个数为奇数的话,那么肯定是无效字符串,直接返回false
注意:如果字符串的最后一个为左括号的话,那肯定也是无效字符串,直接返回false。反之,如果字符串的第一个为右括号的话,那肯定也是无效字符串
# 解法一
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
//空字符串可被认为是有效字符串。
if(s=="") return true
//如果字符串个数为奇数的话,那么肯定是无效字符串,直接返回false
if(s.length % 2 === 1) return false;
//如果字符串的最后一个为左括号的话,那肯定也是无效字符串,直接返回false
if(s[s.length-1]=='(' || s[s.length-1]=='{' || s[s.length-1]=='[') return false;
//如果字符串的第一个为右括号的话,那肯定也是无效字符串
if(s[0]==')' || s[0]=='}' || s[0]==']') return false;
const result=[] //存储左括号
for(let i=0;i<s.length;i++){
//左括号全部入栈
if(s[i]=='(' || s[i]=='{' || s[i]=='[') {
result.push(s[i]);
continue;
}
//如果是右括号,判断栈顶是否是对应的左括号,是的话弹出栈顶
if(s[i]==')' && result[result.length-1]=='('){
result.pop()
continue;
}
if(s[i]=='}' && result[result.length-1]=='{'){
result.pop()
continue;
}
if(s[i]==']' && result[result.length-1]=='['){
result.pop()
continue;
}
}
//处理完字符串后如果栈中还有数据说明字符串中括号没有全部匹配,反之没有数据的话说明全部匹配
return result.length==0
};
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
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
# 题解二
在题解一的思路上,优化一下代码的实现,利用key/value的形式来优化速度
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
//空字符串可被认为是有效字符串。
if(s=="") return true
//如果字符串个数为奇数的话,那么肯定是无效字符串,直接返回false
if(s.length % 2 === 1) return false;
//如果字符串的最后一个为左括号的话,那肯定也是无效字符串,直接返回false
if(s[s.length-1]=='(' || s[s.length-1]=='{' || s[s.length-1]=='[') return false;
//如果字符串的第一个为右括号的话,那肯定也是无效字符串
if(s[0]==')' || s[0]=='}' || s[0]==']') return false;
let obj = {
'{': '}',
'(': ')',
'[': ']'
}
let stack = []
for(let i = 0; i < s.length ; i++) {
if(obj[s[i]]) {
stack.push(s[i]);
} else if(s[i] !== obj[stack.pop()]){
return false
}
}
return stack.length === 0
};
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
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