Skip to main content

有效的括号

· 5 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——20题​

💡 参考代码：​

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/**
 * 判断括号字符串是否有效的函数
 * 
 * 算法思路：
 * 1. 使用栈数据结构来匹配括号
 * 2. 遇到左括号时入栈
 * 3. 遇到右括号时检查栈顶是否为对应的左括号
 * 4. 最后检查栈是否为空
 * 
 * @param s 输入的括号字符串
 * @return bool 字符串是否有效
 */
bool isValid(char* s) {
    int len = strlen(s);
    
    // 空字符串被认为是有效的
    if (len == 0) return true;
    
    // 奇数长度的字符串不可能有效
    if (len % 2 != 0) return false;
    
    // 创建栈用于存储左括号，最大长度为字符串长度的一半+1
    char* stack = (char*)malloc((len + 1) * sizeof(char));
    int top = -1; // 栈顶指针，-1表示空栈
    
    // 遍历字符串中的每个字符
    for (int i = 0; i < len; i++) {
        char c = s[i];
        
        // 如果是左括号，入栈
        if (c == '(' || c == '[' || c == '{') {
            stack[++top] = c; // 先增加栈顶指针，再存储字符
        }
        // 如果是右括号，检查匹配
        else {
            // 栈为空但遇到右括号，无效
            if (top == -1) {
                free(stack);
                return false;
            }
            
            // 检查当前右括号是否与栈顶的左括号匹配
            char topChar = stack[top--]; // 取出栈顶元素并减少栈顶指针
            if ((c == ')' && topChar != '(') ||
                (c == ']' && topChar != '[') ||
                (c == '}' && topChar != '{')) {
                free(stack);
                return false;
            }
        }
    }
    
    // 检查栈是否为空（所有括号都正确匹配）
    bool result = (top == -1);
    free(stack); // 释放栈内存
    return result;
}

// 测试函数
int main() {
    // 测试用例
    char* test1 = "()";
    char* test2 = "()[]{}";
    char* test3 = "(]";
    char* test4 = "([])";
    char* test5 = "([)]";
    
    printf("Test 1: %s -> %s\n", test1, isValid(test1) ? "true" : "false");
    printf("Test 2: %s -> %s\n", test2, isValid(test2) ? "true" : "false");
    printf("Test 3: %s -> %s\n", test3, isValid(test3) ? "true" : "false");
    printf("Test 4: %s -> %s\n", test4, isValid(test4) ? "true" : "false");
    printf("Test 5: %s -> %s\n", test5, isValid(test5) ? "true" : "false");
    
    return 0;
}

📖 总结：​

点击展开题目总结

🤔 有效的括号

1️⃣ 题目核心信息​

🎯 功能描述：判断一个只包含括号字符的字符串是否有效，即所有括号都正确匹配且顺序正确

📥 输入输出：

  • 输入：char* s - 只包含 '(', ')', ', ', '[', ']' 的字符串
  • 输出：bool - 字符串是否有效，有效返回true，否则返回false

2️⃣ 实现原理​

💡 核心思路：使用栈数据结构来匹配括号。遇到左括号入栈，遇到右括号则检查栈顶是否为对应的左括号

📋 实现步骤：

  1. 遍历字符串中的每个字符
  2. 如果是左括号，则将其压入栈中
  3. 如果是右括号，则检查栈是否为空以及栈顶元素是否为对应的左括号
  4. 遍历完成后，检查栈是否为空以确认所有括号都已正确匹配

3️⃣ 关键点解析​

使用栈来处理括号匹配问题是标准解法，通过先进后出的特性确保括号按正确顺序匹配。

🎯 代码技巧​

  • 使用数组模拟栈结构，提高效率
  • 提前处理奇数长度字符串的特殊情况
  • 巧妙使用ASCII码值关系判断括号匹配

4️⃣ 使用场景​

✅ 适用情况：​

  • 编译器语法检查
  • 数学表达式验证
  • 代码编辑器括号匹配功能

⚠️ 前提条件：​

  • 输入字符串只包含指定的括号字符
  • 字符串长度有限制（受系统内存限制）

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，其中n是字符串的长度，需要遍历一次字符串

  • 💾 空间复杂度：O(n)，最坏情况下需要将所有字符存储在栈中

6️⃣ 注意事项​

🚩 边界情况：​

  • 空字符串：被认为是有效的
  • 只包含左括号：无效
  • 只包含右括号：无效

💥 易错点：​

  • 忘记检查栈为空时遇到右括号的情况
  • 忘记检查最后栈是否为空
  • 括号匹配关系判断错误

7️⃣ 补充说明​

以下是对字符串 s = "([{}])" 的执行过程分析：

  1. 初始状态：

    • len = 6
    • stack = [] (空数组)
    • top = -1

  2. 处理第一个字符 '('：

    • current = '('，是左括号
    • 入栈：top = 0，stack[0] = '('

  3. 处理第二个字符 '['：

    • current = '['，是左括号
    • 入栈：top = 1，stack[1] = '['

  4. 处理第三个字符 '{'：

    • current = '{'，是左括号
    • 入栈：top = 2，stack[2] = '{'

  5. 处理第四个字符 '}'：

    • current = '}'，是右括号
    • 检查栈顶：topElement = stack[2] = '{'
    • 匹配成功：'{' 对应 '}'
    • 出栈：top = 1

  6. 处理第五个字符 ']'：

    • current = ']'，是右括号
    • 检查栈顶：topElement = stack[1] = '['
    • 匹配成功：'[' 对应 ']'
    • 出栈：top = 0

  7. 处理第六个字符 ')'：

    • current = ')'，是右括号
    • 检查栈顶：topElement = stack[0] = '('
    • 匹配成功：'(' 对应 ')'
    • 出栈：top = -1

  8. 最终检查：

    • top = -1，栈为空
    • 返回 true，表示字符串有效

通过这个例子可以看出，算法能够正确地处理嵌套括号的情况，并按照后进先出的原则进行匹配检查。

加载评论中...