有效的括号（20）

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例

输入: "()" 输出: true

输入: "()[]{}" 输出: true

输入: "(]" 输出: false

输入: "([)]" 输出: false

输入: "{[]}" 输出: true

算法

栈

维护一个栈，当遇到左边的括号时推入栈，遇到右边的括号时：如果刚好和栈中最后一个括号相同，那么推出栈，否则直接返回false

如果最后栈中没有元素，则说明整个字符串是合法的

export const isValid = (s) => {
	const queue = [];
	for (let i = 0; i < s.length; i++) {
		if (
			(s[i] === ")" && queue[queue.length - 1] === "(") ||
			(s[i] === "]" && queue[queue.length - 1] === "[") ||
			(s[i] === "}" && queue[queue.length - 1] === "{")
		) {
			queue.pop();
		} else if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
			queue.push(s[i]);
		} else {
			return false;
		}
	}
	return queue.length === 0;
};

使用Map

类似方法一，也是维护一个栈，只是使用Map来维护括号之间的关系

export const isValid = (s) => {
	const queue = [];
	const map = new Map();
	map.set(")", "(");
	map.set("}", "{");
	map.set("]", "[");
	for (let i = 0; i < s.length; i++) {
		if (map.has(s[i])) {
			if (map.get(s[i]) === queue[queue.length - 1]) {
				queue.pop();
			} else {
				return false;
			}
		} else {
			queue.push(s[i]);
		}
	}
	return queue.length === 0;
};