跳至主要內容

20. 有效的括号


20. 有效的括号open in new window

🟢   🔖  字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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括号生成open in new window[✓]字符串 动态规划 回溯
32最长有效括号open in new window[✓] 字符串 动态规划
301删除无效的括号open in new window广度优先搜索 字符串 回溯
1003检查替换后的词是否有效open in new window 字符串
2116判断一个括号字符串是否有效open in new window 贪心 字符串
2337移动片段得到字符串open in new window双指针 字符串