力扣经典150题第五十一题：有效的括号

用户8589624

发布于 2025-11-13 16:11:53

1040

文章被收录于专栏：nginxnginx

题目描述和要求

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

有效字符串需满足：

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

示例解释

示例 1：

输入：s = “()” 输出：true

示例 2：

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

示例 3：

输入：s = “(]” 输出：false

解题思路

可以使用栈来解决这个问题。遍历字符串，遇到左括号则入栈，遇到右括号则出栈。如果当前右括号与栈顶的左括号不匹配，则字符串无效。最后，如果栈为空，则字符串有效，否则无效。

算法实现

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为字符串 s 的长度。遍历一次字符串。
空间复杂度：O(n)，最坏情况下栈的空间复杂度为 O(n)。

测试和验证

编写测试用例对算法进行验证，确保其正确性和健壮性。

public class Main {
    public static void main(String[] args) {
        ValidParentheses validParentheses = new ValidParentheses();

        String s1 = "()";
        System.out.println(validParentheses.isValid(s1)); // true

        String s2 = "()[]{}";
        System.out.println(validParentheses.isValid(s2)); // true

        String s3 = "(]";
        System.out.println(validParentheses.isValid(s3)); // false
    }
}