20. 有效的括号
20. 有效的括号
题目
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 10^4
s
consists of parentheses only'()[]{}'
.
题目大意
括号匹配问题。
解题思路
用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;
当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(
”跟“)
”匹配,“[
”跟“]
”匹配,“{
”跟“}
”匹配,则继续扫描剩下的字符串。
如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。
当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。
需要注意,空字符串是满足括号匹配的,即输出 true
。
代码
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
const len = s.length;
if (len === 0) return true;
let stack = [];
for (let i = 0; i < len; i++) {
let v = s[i];
if (v === '{' || v === '(' || v === '[') {
stack.push(v);
} else if (
(v === '}' && stack.length > 0 && stack[stack.length - 1] === '{') ||
(v === ')' && stack.length > 0 && stack[stack.length - 1] === '(') ||
(v === ']' && stack.length > 0 && stack[stack.length - 1] === '[')
) {
stack.pop();
} else {
return false;
}
}
return stack.length === 0;
};
// 简化写法
var isValid = function (s) {
let stack = [],
obj = {
')': '(',
']': '[',
'}': '{'
};
for (let item of s) {
if ('[{('.indexOf(item) != -1) {
stack.push(item);
} else if (obj[item] != stack.pop()) {
return false;
}
}
return stack.length == 0;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
22 | 括号生成 | [✓] | 字符串 动态规划 回溯 | |
32 | 最长有效括号 | [✓] | 栈 字符串 动态规划 | |
301 | 删除无效的括号 | 广度优先搜索 字符串 回溯 | ||
1003 | 检查替换后的词是否有效 | 栈 字符串 | ||
2116 | 判断一个括号字符串是否有效 | 栈 贪心 字符串 | ||
2337 | 移动片段得到字符串 | 双指针 字符串 |