LeetCode 热题 100_有效的括号（69_20_简单_C++）（栈；栈+哈希表（建立左右括号的对应关系））

题目描述：

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。

输入输出样例：

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([])”
输出：true

提示：
1 <= s.length <= 10⁴
s 仅由括号 ‘()[]{}’ 组成

题解：

解题思路：

思路一（栈）：

1、解决此问题时：
① 先检查数组中元素的个数，如果为偶数，则有可能是有效的括号。如果为奇数，则不可能为有效的括号返回false。
② 当是左括号时，左括号入栈。
③ 当是右括号时，栈顶存在与之对应的左括号，则左括号出栈。若不存在与之对应的左括号则返回false。
④ 若最后栈为空则返回true，否则返回false。

2、复杂度分析：
① 时间复杂度：O(n)，n 是字符串 s 的长度。
② 空间复杂度：O(n)，n 是字符串 s 的长度，栈中字符数最多为 n，例如全是左括号，栈中的字符数量为 O(n)

思路二（栈+哈希表（建立左右括号的对应关系））：

1、与思路一的唯一不同在于，将左右括号的对应关系存储在哈希表中，key存储右括号，value存储左括号（因左括号只有入栈的操作，而右括号需判断栈顶有没有与之对应的左括号）。

2、复杂度分析
① 时间复杂度：O(n)，n 是字符串 s 的长度。
② 空间复杂度：O(n+∣Σ∣)，n 是字符串 s 的长度，Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中字符数最多为 n（例如全是左括号），栈中的字符数量为 O(n)。当 n 足够大时∣Σ∣可忽略。

代码实现

代码实现（思路一（栈））：

class Solution1 {
public:bool isValid(string s) {// 如果字符串长度是奇数，返回falseif (s.size() % 2 == 1) return false;stack<char> stk; // 定义一个栈用于存储左括号for (const auto &ch : s) { // 遍历字符串中的每个字符// 如果字符是左括号，则压入栈中if (ch == '(' || ch == '[' || ch == '{') {stk.push(ch);}// 如果当前是右括号但栈为空，说明没有对应的左括号else if (stk.empty() && (ch == ')' || ch == ']' || ch == '}')) {return false;}// 如果是右括号且栈顶元素与之匹配，则弹出栈顶元素else if (ch == ')' && stk.top() == '(') {stk.pop();} else if (ch == ']' && stk.top() == '[') {stk.pop();} else if (ch == '}' && stk.top() == '{') {stk.pop();} else {// 否则返回false，说明不匹配return false;}}// 最后检查栈是否为空，空则有效，非空则无效return stk.empty();}
};

代码实现（思路二（栈+哈希表（建立左右括号的对应关系）））：

class Solution2 {
public:bool isValid(string s) {//如果左右括号总数是奇数，直接返回falseif (s.size()%2==1) return false;//创建左右括号的对应关系，注意key=右括号，value=左括号（因左括号直接入栈无其他情况）unordered_map<char,char> mp={{')','('},{']','['},{'}','{'}};stack<char> stk;//对字符串中的每个字符进行判断for (const auto &ch :s){//如果是右括号if (mp.count(ch)){//当右括号且栈空或者左右括号不匹配返回false匹配失败if (stk.empty() || stk.top()!=mp[ch]){return false;}//当左右括号对应则出栈else{stk.pop();}//左括号直接入栈}else{stk.push(ch);}}//如果最后栈为空则返回true，否则返回false（其中只有左括号）return stk.empty();}
};

以思路二为例进行调试

#include<iostream>
#include<stack>
#include<unordered_map>
using namespace std;class Solution2 {
public:bool isValid(string s) {//如果左右括号总数是奇数，直接返回falseif (s.size()%2==1) return false;//创建左右括号的对应关系，注意key=右括号，value=左括号（因左括号直接入栈无其他情况）unordered_map<char,char> mp={{')','('},{']','['},{'}','{'}};stack<char> stk;//对字符串中的每个字符进行判断for (const auto &ch :s){//如果是右括号if (mp.count(ch)){//当右括号且栈空或者左右括号不匹配返回false匹配失败if (stk.empty() || stk.top()!=mp[ch]){return false;}//当左右括号对应则出栈else{stk.pop();}//左括号直接入栈}else{stk.push(ch);}}//如果最后栈为空则返回true，否则返回false（其中只有左括号）return stk.empty();}
};int main(int argc, char const *argv[])
{string s="((()))";//判断有效的括号Solution2 s2;if (s2.isValid(s)){cout<<"true"<<endl;}else{cout<<"false"<<endl;}return 0;
}

LeetCode 热题 100_有效的括号（69_20)原题链接
欢迎大家和我沟通交流(✿◠‿◠)