020.有效的括号
Zsh's Blog 2019-08-06
描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路
- 利用栈的先进后出特点
- 遍历每一个字符，如果与栈顶元素匹配，则出栈，不匹配则进栈；最后为空栈说明是合法的。
如果遇到开括号，我们只需将其推到栈上即可。如果遇到一个闭括号，检查栈顶的元素是一个相同类型的左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。 如果到最后我们剩下的栈中仍然有元素，那么这意味着括号不是有效的
代码
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let map = {
'[': ']',
'(': ')',
'{': '}'
}
let arr = s.split('')
let stack = []
for (let i = 0; i < arr.length; i++) {
if (map[stack[stack.length - 1]] === arr[i]) {
stack.pop()
} else {
stack.push(arr[i])
}
}
if (stack.length == 0) {
return true
}
return 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
用 '()[]{}' 例子来说明，初始化时 stack 为 []
第一次 ( 入栈，stack 为 ['(']，
第二次 ) 入栈，与栈顶元素进行比较，即 stack[stack.length - 1]，发现能在 map 中匹配上，则将 ( 出栈，stack 为 []
如果不能匹配，比如是 ]，则入栈，即 stack 为 ['(',']']，继续循环
直到 stack 中是空数组，说明输入的括号是有效的，如果还有值，则说明无效
测试
test('有效的括号', () => {
expect(isValid('()')).toBe(true)
expect(isValid('()[]{}')).toBe(true)
expect(isValid('(]')).toBe(false)
expect(isValid('([)]')).toBe(false)
expect(isValid('{[]}')).toBe(true)
})
1
2
3
4
5
6
7
2
3
4
5
6
7