LeetCode
栈结构
栈 => 后进先出
题解
typescript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
// 1. 如果字符串length为奇数, 肯定不匹配
if (s.length % 2 === 1) return false
// 2. 栈结构处理,左括号,入栈,右括号,出栈; 数组的最后一个作为栈顶
const stack = []
for (let i = 0; i < s.length; i++) {
const char = s[i]
if (char === '(' || char === '{' || char === '[') {
stack.push(char)
} else {
// 出栈,并和栈顶对比, 如果匹配,就出栈
const top = stack[stack.length - 1]
if (
(top === '(' && char === ')') ||
(top === '[' && char === ']') ||
(top === '{' && char === '}')
) {
stack.pop()
} else {
return false
}
}
}
// 最后,栈应该为空,如果不为空,说明有未闭合的括号
return stack.length === 0
}
代码简化,用map结构定义左右括号的关系
typescript
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
// 1. 如果字符串length为奇数, 肯定不匹配
if (s.length % 2 === 1) return false
// 2. 栈结构处理,左括号,入栈,右括号,出栈; 数组的最后一个作为栈顶
const stack = []
// 3. map定义左右括号对应关系
const map = {
'(': ')',
'{': '}',
'[': ']'
}
for (let i = 0; i < s.length; i++) {
const char = s[i]
if (map[char]) {
// 左括号,入栈
stack.push(char)
} else {
// 如果是右括号,检查是否与栈顶的左括号匹配
// 匹配直接出栈
const top = stack.pop()
if (char !== map[top]) {
return false
}
}
}
// 最后,栈应该为空,如果不为空,说明有未闭合的左括号 Error
return stack.length === 0
}