【20. 有效的括号】

前言

在这道题目中需要判断一个只包含括号的字符串是否有效。一个有效的字符串需要满足：

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

括号类型包括：

• 圆括号：() 和 )
• 方括号：[ 和 ]
• 花括号：{ 和 }

解题思路

使用 栈 数据结构。栈的特性是 后进先出（LIFO）。

1. 初始化数据结构：我们需要一个栈来存放未匹配的左括号，同时用一个哈希表来存储右括号与左括号的对应关系。

2. 遍历字符串：

   • 如果遇到左括号（(, {, [），将其压入栈中。
   • 如果遇到右括号（), }, ]），检查栈顶是否有相应类型的左括号匹配：
     • 如果匹配，则弹出栈顶元素。
     • 如果不匹配或者栈为空，则字符串无效。

3. 最终检查：遍历结束后，如果栈为空，则所有左括号都有相应的右括号匹配，字符串有效；否则，字符串无效。

代码实现

#include <iostream> #include <stack> #include <unordered_map>  using namespace std;  class Solution { public:     bool isValid(string s) {         // 哈希表用于存储右括号与左括号的对应关系         unordered_map<char, char> bracket_map = {             {')', '('},             {'}', '{'},             {']', '['}         };          // 栈用于存储未匹配的左括号         stack<char> stack;          for (char ch : s) {             if (bracket_map.count(ch)) {                 // 如果当前字符是右括号                 if (!stack.empty() && stack.top() == bracket_map[ch]) {                     stack.pop(); // 配对成功，弹出栈顶的左括号                 } else {                     return false; // 配对失败                 }             } else {                 // 当前字符是左括号，压入栈中                 stack.push(ch);             }         }          // 栈为空说明所有左括号都有匹配的右括号         return stack.empty();     } };  int main() {     Solution solution;     string s;     cin >> s;     if (solution.isValid(s)) {         cout << "True" << endl;     } else {         cout << "False" << endl;     }     return 0; } 

代码讲解

• 哈希表（unordered_map）：

  • 用于存储右括号与左括号的对应关系。这样在遇到右括号时，可以快速查找它对应的左括号。

• 栈（stack<char>）：

  • 用于存储未匹配的左括号。当遇到右括号时，检查栈顶是否有相应的左括号匹配，如果匹配则弹出栈顶，否则返回 false。

• 遍历字符串：

  • 遍历字符串中的每一个字符，判断是左括号还是右括号，并做相应的操作。

• 最终判断：

  • 遍历结束后，检查栈是否为空。如果为空，说明所有的左括号都有匹配的右括号；否则，有未匹配的左括号存在，返回 false。

总结

该算法的时间复杂度是 O(n)，空间复杂度也是 O(n)，其中 n 是输入字符串的长度。