概述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
测试
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
输入：s = "([)]"
输出：false
输入：s = "{[]}"
输出：true
解题思路
{[()]}
1、需要遍历所有字符串
2、遇到左括号先略过，遇到右括号开始匹配，匹配的是最后遇到的左括号
3、后进先出模式，左括号逐一入栈，若遇到右括号，则取栈顶元素左括号
解题步骤
1、新建一个栈
2、扫描字符串，遇左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法
3、最后栈空了就合法，否则不合法
代码
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if (s.length % 2 === 1) {
return false
}
const stack = []
for (const value of s) {
if (value === '(' || value === '[' || value === '{') {
stack.push(value)
}else {
const stack_top = stack[stack.length-1]
if (
(stack_top === '(' && value === ')') ||
(stack_top === '[' && value === ']') ||
(stack_top === '{' && value === '}')
) {
stack.pop()
}else {
return false
}
}
}
return stack.length === 0
};
var isValid = function(s) {
const length = s.length
if (length % 2 === 1) {
return false
}
const stack = []
let index = -1
while (++index < length) {
const value = s[index]
if (value === '(' || value === '[' || value === '{') {
stack.push(value)
}else {
const stack_top = stack[stack.length-1]
if (
(stack_top === '(' && value === ')') ||
(stack_top === '[' && value === ']') ||
(stack_top === '{' && value === '}')
) {
stack.pop()
}else {
return false
}
}
}
return stack.length === 0
};
复杂度
- 时间复杂度：O(n)，其中 n是字符串 s 的长度。
- 空间复杂度：O(n)
总结
1、栈适合解决对称类问题
2、先分析不合理情况，若存在，则提前返回