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