Easy

题目描述

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

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([])"
输出：true

示例 5：

输入：s = "([)]"
输出：false

约束条件：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

解题思路

解题思路

这是一个经典的栈应用问题。括号匹配的本质是**后进先出（LIFO）**的过程：最后遇到的左括号应该最先被匹配。

核心思路：

  1. 使用栈来存储遇到的左括号
  2. 遇到左括号 (、[、{ 时，将其压入栈中
  3. 遇到右括号 )、]、} 时，检查栈顶元素是否为对应的左括号
    • 如果匹配，弹出栈顶元素继续处理
    • 如果不匹配或栈为空，说明括号无效
  4. 最后检查栈是否为空，空栈表示所有括号都正确匹配

边界情况处理：

  • 字符串长度为奇数时，必定无效
  • 遇到右括号但栈为空时，说明缺少对应的左括号
  • 处理完所有字符后栈不为空，说明有未匹配的左括号

时间复杂度优化： 可以使用哈希表存储括号对应关系，避免多次条件判断，提高代码可读性。

这种栈-based的解法是最直观且高效的方案，时间复杂度O(n)，空间复杂度O(n)。

代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) return false;
                
                char top = st.top();
                st.pop();
                
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        return st.empty();
    }
};

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}
        
        for char in s:
            if char in mapping:
                if not stack or stack.pop() != mapping[char]:
                    return False
            else:
                stack.append(char)
        
        return not stack

public class Solution {
    public bool IsValid(string s) {
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in s) {
            if (c == '(' || c == '[' || c == '{') {
                stack.Push(c);
            } else {
                if (stack.Count == 0) return false;
                
                char top = stack.Pop();
                
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        return stack.Count == 0;
    }
}

var isValid = function(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };
    
    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            if (stack.length === 0 || stack.pop() !== map[char]) {
                return false;
            }
        }
    }
    
    return stack.length === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串中的每个字符一次
空间复杂度O(n)最坏情况下栈中存储所有的左括号

相关题目