要点:有效的括号、栈
描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true 示例 2:
输入: "()[]{}" 输出: true 示例 3:
输入: "(]" 输出: false 示例 4:
输入: "([)]" 输出: false 示例 5:
输入: "{[]}" 输出: true
|
思路
使用栈,遍历输入字符串
如果当前字符为左半边括号时,则将其压入栈中
如果遇到右半边括号时,分类讨论:
1)如栈不为空且为对应的左半边括号,则取出栈顶元素,继续循环
2)若此时栈为空,则直接返回 false
3)若不为对应的左半边括号,反之返回 false
题解
方法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
const isValid = function(s) { const stack = [] for (let i = 0; i < s.length; i++) { const c = s[i] switch (c) { case '(': stack.push(')') break case '{': stack.push('}') break case '[': stack.push(']') break default: if (c !== stack.pop()) { return false; } } } return stack.length === 0; };
|
- 91/91 cases passed (68 ms)
- Your runtime beats 87.56 % of javascript submissions
- Your memory usage beats 97.17 % of javascript submissions (37.6 MB)
时间复杂度:$O(N)$
空间复杂度:$O(N)$
方法二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| var isValid = function(s) { const stack = [], map = { "(":")", "{":"}", "[":"]" }; for(const x of s) { if(x in map) { stack.push(x); console.log('入栈:'+x) continue; }; console.log('出栈:'+x) if(map[stack.pop()] !== x) return false; } return !stack.length; };
console.log(isValid('({})'))
入栈:( 入栈:{ 出栈:} 出栈:) true
|
- 91/91 cases passed (60 ms)
- Your runtime beats 98.53 % of javascript submissions
- Your memory usage beats 60.39 % of javascript submissions (38.2 MB)
时间复杂度:$O(N)$
空间复杂度:$O(N)$
方法三
正则解析
1 2 3 4 5 6 7 8 9 10 11
|
var isValid = function (s) { while (s.includes("[]") || s.includes("()") || s.includes("{}")) { s = s.replace("[]", "").replace("()", "").replace("{}", ""); } s = s.replace("[]", "").replace("()", "").replace("{}", ""); return s.length === 0; };
|
- 91/91 cases passed (116 ms)
- Your runtime beats 6.64 % of javascript submissions
- Your memory usage beats 5.19 % of javascript submissions (43.3 MB)
时间复杂度:取决于正则引擎的实现
空间复杂度:取决于正则引擎的实现
Tips:
Please indicate the source and original author when reprinting or quoting this article.