题目来源:. - 力扣(LeetCode)
题目思路分析
题目是关于验证括号字符串是否有效的经典问题。一个括号字符串是有效的,当且仅当它满足以下条件:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
例如,字符串 "()" 和 "()[]{}" 是有效的,而 "(]" 和 "(()" 则不是有效的括号字符串。
解题思路:
- 使用栈(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)遍历字符串中的每个字符。
通过这道题,我们学习了如何使用栈数据结构来解决括号匹配问题。这种方法不仅简单易懂,而且非常高效。在实际应用中,栈和哈希表等数据结构是解决问题的有力工具,掌握它们可以大大提高我们的编程能力和解决问题的能力。希望这篇文章能帮助大家更好地理解这个问题,并学会使用栈和哈希表来解决类似的问题。