一、问题描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
题目链接：有效的括号
二、题目要求
样例 1
输入： s = "()" 输出： true
样例 2
输入： s = "([)]" 输出： false
考察
字符串、栈、哈希 建议用时20~35min
三、问题分析
这一题需要用到栈的相关知识点，如果没了解过栈的可以看一下这一篇文章，栈其实就是先进后出的存储结构。
对于这一题的有效括号，我们可以先定义哈希表m特定化不同的6个括号。
map<char,int>m={{'(',1},{'{',2},{'[',3}, {')',4},{'}',5},{']',6}};
只要前3个括号出现，那么就存储到栈里面去，后三个出现那么肯定要进行括号匹配消除的。 消除的话，如果和栈第一个括号匹配成功，那么就弹出栈顶。
如果匹配不成功，后三个括号入栈，那就完了，因为无论你后面有再多的括号，它也匹配不了，直接退出就行。
四、编码实现
classSolution { public: boolisValid(strings) { inti,n=s.size();//初始化数据boolflag=true;//一开始判断匹配成功stack<char>k; map<char,int>m={{'(',1},{'{',2},{'[',3},//哈希存储括号 {')',4},{'}',5},{']',6}}; for(i=0;i<n;i++)//循环判断 { if(m[s[i]]<=3)//前三个直接存储k.push(s[i]); elseif(!k.empty()&&m[s[i]]-3==m[k.top()])//后三个与栈顶匹配消除k.pop(); else//匹配失败 { flag=false; break; } } if(!k.empty())//如果栈不为空，那也匹配失败flag=false; returnflag;//返回结果 } };
