Open qappleh opened 3 years ago
解题思路: 将字符串中的字符依次入栈,遍历字符依次判断:
当遍历完成时,所有已匹配的字符都已匹配出栈,如果此时栈为空,则字符串有效,如果栈不为空,说明字符串中还有未匹配的字符,字符串无效
画图帮助理解一下:
代码实现:
var isValid = function(s) {
let map = {
'{': '}',
'(': ')',
'[': ']'
}
let stack = []
for(let i = 0; i < s.length ; i++) {
if(map[s[i]]) {
stack.push(s[i])
} else if(s[i] !== map[stack.pop()]){
return false
}
}
return stack.length === 0
};
时间复杂度:O(n)
空间复杂度:O(n)
给定一个只包括 '(' ,')' ,'{' ,'}' ,'[' ,']' 的字符串,判断字符串是否有效。
有效字符串需满足:
注意空字符串可被认为是有效字符串。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5: