| 链接 | 有效的括号 |
|---|---|
| 题序号 | 20 |
| 题型 | 字符串 |
| 解法 | 栈 |
| 难度 | 简单 |
| 熟练度 | ✅✅✅ |
题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([])”
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
题解
- 核心思想：判断括号是否有效，关键在于匹配。我们需要确保每个左括号都能找到对应的右括号，并且它们的顺序是正确的。为此，可以使用栈（Stack）来实现。
- 栈（stack）：
- 复杂度：时间复杂度为O(n)，其中 n 是字符串 s 的长度。空间复杂度为O(n)，由栈的大小决定，哈希表的空间是常数项，因为常数项在大O表示法中是可以忽略的。这意味着算法的空间需求主要取决于输入数据的大小，而与字符集的大小无关。
- c++ 实现算法：
bool isValid(string s) {// 用栈保存未匹配的左括号stack<char> st;// 使用哈希表存储括号的映射关系//键（Key）：右括号，包括 ')'、']' 和 '}'。//值（Value）：对应的左括号，包括 '('、'[' 和 '{'。unordered_map<char, char> brackets = {{')', '('},{']', '['},{'}', '{'}};for (char c : s) {// 如果是右括号//在 unordered_map 中，count(key) 用于检查给定的 键key 是否存在于哈希表中//如果 key 存在，返回 1. 如果 键key 不存在，返回 0if (brackets.count(c)) {// 栈顶字符与右括号的匹配//检查栈是否为空，或者栈顶是否与当前右括号的匹配左括号相同//通过 brackets[c] 找到右括号对应的左括号，如果 c 是 ')'，brackets[c] 就是 '('。if (!st.empty() && st.top() == brackets[c]) {st.pop(); // 匹配成功，移除栈顶} else {return false; // 匹配失败}} else {// 如果是左括号，入栈st.push(c);}}// 栈为空表示所有括号都匹配成功return st.empty();
}
- 算法推演：
以输入 s = “{[()]}” 为例：
- 遍历字符 ‘{’：入栈 st = [‘{’]。
- 遍历字符 ‘[’：入栈 st = [‘{’, ‘[’]。
- 遍历字符 ‘(’：入栈 st = [‘{’, ‘[’, ‘(’]。
- 遍历字符 ‘)’： 栈顶为 ‘(’，匹配成功，弹出栈顶 st = [‘{’, ‘[’]。
- 遍历字符’]‘： 栈顶为 ‘[’，匹配成功，弹出栈顶 st = [’{']。
- 遍历字符 ‘}’： 栈顶为 ‘{’，匹配成功，弹出栈顶 st = []。
遍历结束，栈为空，返回 true。
- c++ 完整demo：
#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>using namespace std;bool isValid(string s) {// 用栈保存未匹配的左括号stack<char> st;// 使用哈希表存储括号的映射关系//键（Key）：右括号，包括 ')'、']' 和 '}'。//值（Value）：对应的左括号，包括 '('、'[' 和 '{'。unordered_map<char, char> brackets = {{')', '('},{']', '['},{'}', '{'}};for (char c : s) {// 如果是右括号//在 unordered_map 中，count(key) 用于检查给定的 键key 是否存在于哈希表中//如果 key 存在，返回 1. 如果 键key 不存在，返回 0if (brackets.count(c)) {// 栈顶字符与右括号的匹配//检查栈是否为空，或者栈顶是否与当前右括号的匹配左括号相同//通过 brackets[c] 找到右括号对应的左括号，如果 c 是 ')'，brackets[c] 就是 '('。if (!st.empty() && st.top() == brackets[c]) {st.pop(); // 匹配成功，移除栈顶} else {return false; // 匹配失败}} else {// 如果是左括号，入栈st.push(c);}}// 栈为空表示所有括号都匹配成功return st.empty();
}int main() {string s = "{[()]}";if (isValid(s)) {cout << "true" << endl;} else {cout << "false" << endl;}return 0;
}
