有效的括号
有效的括号
用户4456933
发布于 2021-06-01 06:57:03
发布于 2021-06-01 06:57:03
代码可运行
运行总次数：0
代码可运行
有效的括号
难度：简单 来源：20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路：
- 括号必须是成对出现的，所以字符串长度一定是偶数；
- 括号必须是成对出现的，这个机制和 Map 这种一一对应的映射关系一致，所以可以用 Map 来映射它们之间的关系；
- 当遍历字符串的时候，如果是左括号（Map 的键）则压入栈中，否则它一定是右括号，则需要用栈最后一位存的 Map 键去取对应的值然后和当前字符匹配，如果匹配则把栈中的最后一位键出栈，否则 返回 false
- 优化：当遍历字符串的时候，如果当前字符是右括号，则说明前面一定出现过左括号即栈中一定压入了数据，所以此时栈的长度不应该为 0；
- 最后，如果一个字符串是括号顺序匹配的，那么栈中不应该存在字符，即所有被压入栈中的左括号都已经因为匹配到了右括号而被出栈，所以此时的栈长度应该为 0；
题解：
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let l = s.length
if (l % 2 !== 0) return false
let stack = []
let map = new Map([
['(', ')'],
['[', ']'],
['{', '}']
])
for (let i = 0; i < l; i++) {
if (map.has(s[i])) {
stack.push(s[i])
} else {
if (stack.length === 0) return false
if (map.get(stack[stack.length - 1]) === s[i]) stack.pop()
else return false
}
}
return stack.length === 0
};
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-01-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
