20.有效的括号

题目:20.有效的括号

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

有效字符串需满足：

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

• 示例 1：

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

• 示例 2：

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

• 示例 3：

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

• 提示：

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

思路1

要判断给定的字符串是否是一个有效的括号字符串，我们可以使用栈来解决这个问题。栈的数据结构特性非常适合这种括号匹配的场景，因为栈遵循后进先出的原则，可以有效地处理嵌套的括号结构。

1. 初始化一个栈：我们使用一个栈来保存遇到的左括号。
2. 遍历字符串：遍历字符串中的每一个字符：
   • 如果是左括号（(, {, [），则将其推入栈中。
   • 如果是右括号（), }, ]），则检查栈是否为空。如果栈为空，说明没有对应的左括号，直接返回 false。否则检查弹出的左括号是否与当前右括号匹配：如果匹配，就弹出左括号，如果不匹配就推入右括号。
3. 检查栈是否为空：遍历结束后，如果栈为空，说明所有的括号都匹配，返回 true。否则，返回 false，因为还有未匹配的左括号。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            // 如果是左括号，则将其推入栈中
            stack.push(c);
        } else {
            // 如果是右括号，先检查栈是否为空
            if (stack.isEmpty()) {
                return false;
            }
            // 检查弹出的左括号是否与当前右括号匹配：如果匹配，就弹出左括号，如果不匹配就推入右括号
            Character peek = stack.peek();
            if (c == ')' && peek == '(') {
                stack.pop();
            } else if (c == '}' && peek == '{') {
                stack.pop();
            } else if (c == ']' && peek == '[') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
    }
    return stack.isEmpty();
}

思路2

1. 初始化一个栈：我们使用一个栈来保存遇到的左括号。
2. 遍历字符串：遍历字符串中的每一个字符：
   • 如果是左括号（(, {, [），则将其推入栈中。
   • 如果是右括号（), }, ]），则检查栈是否为空。如果栈为空，说明没有对应的左括号，直接返回 false。否则，从栈顶弹出一个左括号，并检查弹出的左括号是否与当前的右括号匹配。如果不匹配，返回 false。
3. 检查栈是否为空：遍历结束后，如果栈为空，说明所有的括号都匹配，返回 true。否则，返回 false，因为还有未匹配的左括号。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            // 如果是左括号，则将其推入栈中
            stack.push(c);
        } else {
            // 如果是右括号，先检查栈是否为空
            if (stack.isEmpty()) {
                return false;
            }
            // 检查弹出的左括号是否与当前右括号匹配
            Character top = stack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}