ccDocs

外观

导航栏

LeetCode 20. 有效的括号 简单 ​

题目描述 ​

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

有效字符串需满足：

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

示例 1:

javascript
输入: "()";
输出: true;

示例 2:

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

示例 3:

javascript
输入: "(]";
输出: false;

示例 4:

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

示例 5:

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

题解 ​

发现越靠后的左括号，最先匹配，也就是后进先出的思想，于是考虑使用栈这个数据结构。

首先判断是否满足配对的基本条件-偶数个，减少不必要的计算。接着遍历字符串，如果是左括号，就入栈，如果是右括号，就判断栈顶元素是否与之匹配，如果匹配就出栈，否则返回false。最后判断栈是否为空，如果为空，说明所有的括号都匹配成功，返回true，否则返回false。

javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // 如果是奇数，不可能匹配成功，直接返回false
  if (s.length & 1) return false;
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "{" || s[i] === "[") stack.push(s[i]);
    else if (s[i] === ")" && stack[stack.length - 1] === "(") stack.pop();
    else if (s[i] === "}" && stack[stack.length - 1] === "{") stack.pop();
    else if (s[i] === "]" && stack[stack.length - 1] === "[") stack.pop();
    else return false;
  }
  return !stack.length;
};