原题地址:有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}"
输出: true
栈
本题是栈的典型应用,只需要复用栈先进后出的特点,将左括号入栈,找到对应的右括号后就出栈。如果最后栈为空,证明字符串中的括号对就是有效的:
/**
* @param {string} s
* @return {boolean}
*/
const isValid1 = function(s) {
let stack = [];
let left = ['(', '{', '[']; // 左括号
let right = [')', '}', ']']; // 右括号
for (let i = 0; i < s.length; i ++) {
if (left.includes(s[i])) {
// 左括号入栈
stack.push(s[i]);
} else if (right.includes(s[i])) {
// 栈为空,证明此时这个右括号就是多出来的,肯定不匹配
if (stack.length === 0) {
return false;
}
if (left.indexOf(stack[stack.length - 1]) !== right.indexOf(s[i])) {
// 右括号与此时栈顶的左括号不匹配,证明串中的括号不匹配
return false;
} else {
// 左右括号匹配,则将左括号出栈
stack.pop();
}
}
}
// 如果最后栈为空,则括号匹配,否则不匹配
return stack.length === 0;
};
测试:
let start = new Date();
const test = isValid1;
console.log(test('()')); // true
console.log(test('()[]{}')); // true
console.log(test('(]')); // false
console.log(test('([)]')); // false
console.log(test('{[]}')); // true
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度: 一次遍历,时间复杂度为O(n)
空间复杂度: 最坏情况下串中全为左括号,全入栈,空间复杂度为O(n)
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 28,2019