Liaoyi

外观

本页目录

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;
};
cpp
class Solution {
public:
    bool isValid(string s) {
        if (s.size() & 1) return false;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') st.push(s[i]);
            else if (s[i] == ')' && st.top() == '(') st.pop();
            else if (s[i] == '}' && st.top() == '{') st.pop();
            else if (s[i] == ']' && st.top() == '[') st.pop();
            else return false;
        }
        return st.empty();
    }
};
java
class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') stack.push(s.charAt(i));
            else if (s.charAt(i) == ')' && stack.peek() == '(') stack.pop();
            else if (s.charAt(i) == '}' && stack.peek() == '{') stack.pop();
            else if (s.charAt(i) == ']' && stack.peek() == '[') stack.pop();
            else return false;
        }
        return stack.empty();
    }
}
python
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1: return False
        stack = []
        for i in s:
            if i == '(' or i == '{' or i == '[': stack.append(i)
            elif i == ')' and stack[-1] == '(': stack.pop()
            elif i == '}' and stack[-1] == '{': stack.pop()
            elif i == ']' and stack[-1] == '[': stack.pop()
            else: return False
        return not stack