判断括号字符串是否有效

基本思路

这个问题可以通过使用栈（Stack）来解决。主要思想是：

1. 遇到左括号时入栈
2. 遇到右括号时检查栈顶元素是否匹配
3. 最后检查栈是否为空

具体方法

• 使用一个栈存储未匹配的左括号
• 遍历字符串中的每个字符：
  • 如果是左括号 '('、'['、'{'，直接入栈
  • 如果是右括号 ')'、']'、'}'：
    • 检查栈是否为空（空则无效）
    • 检查栈顶元素是否与当前右括号匹配
• 遍历结束后，检查栈是否为空（不空则无效）

相关算法

• 栈（Stack）：用于存储和匹配括号
• 时间复杂度：O(n)，n为字符串长度
• 空间复杂度：O(n)，最坏情况下所有字符都是左括号

复杂度分析

• 时间复杂度：O(n)
  • 每个字符只遍历一次
  • 栈的push和pop操作都是O(1)
• 空间复杂度：O(n)
  • 最坏情况下，如"(((("，栈需要存储所有字符

代码实现

Python 实现

class Solution:
    def isValid(self, s: str) -> bool:
        # 创建栈
        stack = []
        # 括号匹配字典
        brackets = {')': '(', ']': '[', '}': '{'}
        
        # 遍历字符串
        for char in s:
            # 如果是左括号，入栈
            if char in '([{':
                stack.append(char)
            # 如果是右括号
            elif char in ')]}':
                # 栈为空或栈顶不匹配，返回False
                if not stack or stack.pop() != brackets[char]:
                    return False
        
        # 检查栈是否为空
        return len(stack) == 0

# ACM模式输入输出
if __name__ == "__main__":
    solution = Solution()
    # 读取输入
    s = input().strip()
    # 输出结果
    print(solution.isValid(s))

Java 实现

import java.util.Scanner;

public class Main {
    public class Solution {
        public boolean isValid(String s) {
            // 创建字符数组作为栈
            char[] stack = new char[s.length()];
            int top = -1;  // 栈顶指针
            
            // 遍历字符串
            for (char c : s.toCharArray()) {
                // 如果是左括号，入栈
                if (c == '(' || c == '[' || c == '{') {
                    stack[++top] = c;
                } 
                // 如果是右括号
                else {
                    // 栈为空或不匹配，返回false
                    if (top == -1) return false;
                    char last = stack[top--];
                    if ((c == ')' && last != '(') || 
                        (c == ']' && last != '[') || 
                        (c == '}' && last != '{')) {
                        return false;
                    }
                }
            }
            
            // 检查栈是否为空
            return top == -1;
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Solution solution = main.new Solution();
        // ACM模式输入
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        // 输出结果
        System.out.println(solution.isValid(s) ? "true" : "false");
        sc.close();
    }
}

C++ 实现

#include <string>
#include <stack>
#include <iostream>
using namespace std;
class Solution {
public:
    bool isValid(string s) {
        // 创建栈
        stack<char> stack;
        
        // 遍历字符串
        for (char c : s) {
            // 如果是左括号，入栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } 
            // 如果是右括号
            else {
                // 栈为空，返回false
                if (stack.empty()) return false;
                // 检查是否匹配
                char top = stack.top();
                stack.pop();
                if ((c == ')' && top != '(') || 
                    (c == ']' && top != '[') || 
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        
        // 检查栈是否为空
        return stack.empty();
    }
};

// ACM模式输入输出
int main() {
    Solution solution;
    // 读取输入
    string s;
    getline(cin, s);
    // 输出结果
    cout << (solution.isValid(s) ? "true" : "false") << endl;
    return 0;
}

Leetcode 69.有效的括号-原题链接

题目内容

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

有效字符串需满足：

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

输入描述

输入一个字符串 s。

输出描述

输出 "true" 或 "false"，表示字符串是否有效。不用考虑大小写。

样例1

输入

()

输出

true

样例2

输入

()[]{}

输出

true

样例3

输入

(]

输出

false

样例4

输入

([])

输出

true

提示

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