C++算法练习-day23——20.有效的括号

时间：2024-10-28 07:37:50

题目来源：. - 力扣（LeetCode）

题目思路分析

题目是关于验证括号字符串是否有效的经典问题。一个括号字符串是有效的，当且仅当它满足以下条件：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

例如，字符串 "()" 和 "()[]{}" 是有效的，而 "(]" 和 "(()" 则不是有效的括号字符串。

解题思路：

  • 使用栈（Stack）数据结构来处理括号匹配问题。
  • 遍历字符串中的每个字符：
    • 如果遇到左括号（'(', '[', '{'），将其压入栈中。
    • 如果遇到右括号（')', ']', '}'），检查栈顶元素是否为对应的左括号，如果是，则弹出栈顶元素，否则字符串无效。
  • 最后，如果栈为空，说明所有的括号都成功匹配，字符串有效；否则，字符串无效。

代码：

#include <iostream>  
#include <stack>  
#include <unordered_map>  
#include <string>  
  
using namespace std;  
  
class Solution {  
public:  
    bool isValid(string s) {  
        int n = s.size();  
        // 如果字符串长度为奇数，直接返回false，因为无法匹配  
        if (n % 2 == 1) {  
            return false;  
        }  
          
        // 创建一个哈希表，存储右括号到左括号的映射  
        unordered_map<char, char> pairs = {{'}', '{'}, {']', '['}, {')', '('}};  
        stack<char> stk;  
          
        // 遍历字符串中的每个字符  
        for (char e : s) {  
            // 如果当前字符是右括号  
            if (pairs.count(e)) {  
                // 如果栈为空，或者栈顶元素不是对应的左括号，则字符串无效  
                if (stk.empty() || stk.top() != pairs[e]) {  
                    return false;  
                }  
                // 弹出栈顶元素，表示成功匹配了一对括号  
                stk.pop();  
            } else {  
                // 如果是左括号，则压入栈中  
                stk.push(e);  
            }  
        }  
          
        // 如果栈为空，说明所有括号都成功匹配，返回true  
        // 否则，返回false，表示有未匹配的左括号  
        return stk.empty();  
    }  
};

注释详解

  • unordered_map<char, char> pairs = {{'}', '{'}, {']', '['}, {')', '('}};：创建一个哈希表，用于存储右括号到左括号的映射。
  • stack<char> stk;：创建一个栈，用于存储遍历过程中遇到的左括号。
  • if (n % 2 == 1) { return false; }：如果字符串长度为奇数，直接返回false，因为无法匹配。
  • if (pairs.count(e)) { ... } else { ... }：判断当前字符是否为右括号，如果是则检查栈顶元素，否则将左括号压入栈中。
  • if (stk.empty() || stk.top() != pairs[e]) { return false; }：如果栈为空，或者栈顶元素不是对应的左括号，则返回false。
  • stk.pop();：弹出栈顶元素，表示成功匹配了一对括号。
  • return stk.empty();：最后检查栈是否为空，如果为空则返回true，否则返回false。

知识点摘要

  • 栈（Stack）数据结构：后进先出（LIFO）的数据结构，常用于解决括号匹配等问题。
  • 哈希表（Hash Table）：一种高效的键值对存储结构，支持快速查找。
  • 字符串遍历：使用范围for循环（range-based for loop）遍历字符串中的每个字符。

通过这道题，我们学习了如何使用栈数据结构来解决括号匹配问题。这种方法不仅简单易懂，而且非常高效。在实际应用中，栈和哈希表等数据结构是解决问题的有力工具，掌握它们可以大大提高我们的编程能力和解决问题的能力。希望这篇文章能帮助大家更好地理解这个问题，并学会使用栈和哈希表来解决类似的问题。

相关文章