给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
idea： 使用栈来完成工作。接受左括号就入栈，有括号则与栈顶元素匹配，匹配成功就出栈。在添加一些细节。刚开始不知道如何实现代码，看过题解后，使用哈希表可以方便左右括号的匹配，还可以利用已经封装好的栈方法进行编写。
class Solution { public: bool isValid(string s) { int n = s.size(); //得到字符串元素个数 if(n%2==1){ //单数则不可能满足匹配 return false; } unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; //建立哈希表，注意左右括号输入顺序 stack<char> hole; //创建栈 for(char c: s){ //依次遍历字符串s if( pairs.count(c) ){ //如果当前字符为右括号，则开始匹配 if(!hole.empty() && hole.top() == pairs[c]){ //栈不为空且栈顶元素与当前字符匹配成功，则出栈，继续遍历 hole.pop(); continue; } else{ return false; } } hole.push(c); //当前字符为不为右括号则入栈 } return hole.empty(); //要求最后栈为空则返回true } };
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 是字符串 ss 的长度。
空间复杂度：O(n + |\Sigma|)O(n+∣Σ∣)，其中 \SigmaΣ 表示字符集，本题中字符串只包含 66 种括号，|\Sigma| = 6∣Σ∣=6。栈中的字符数量为 O(n)O(n)，而哈希表使用的空间为 O(|\Sigma|)O(∣Σ∣)，相加即可得到总空间复杂度。
法二： idea：一样的思路，不过哈希表的写法有些许差别
class Solution {
public:
bool isValid(string s) {
unordered_map<char,int> m{ {'(', 1} , { '[' , 2 } , { '{' , 3 }, { ')' , 4 } , { ']' , 5 } , { '}' , 6 } }; //用int值记录对应相应括号，且左括号顺序与右括号顺序相同，方便对应
stack<char> st;
bool istrue=true;
for(char c:s){
int flag=m[c];
if(flag>=1&&flag<=3) st.push(c); //左括号就入栈
else if(!st.empty()&&m[st.top()]==flag-3) st.pop(); //右括号就出栈
else {istrue=false;break;} //栈为空就返回
}
if(!st.empty()) istrue=false; //最后栈为空判断返回值
return istrue;
}
};
复杂度分析
时间复杂度：O(N)O(N)。遍历了一遍字符串。
空间复杂度：O(N)O(N)。最坏情况下，假如输入是 (((((((，栈的大小将是输入字符串的长度。
作者：z1m
链接：https://leetcode.cn/problems/valid-parentheses/solution/zhu-bu-fen-xi-tu-jie-zhan-zhan-shi-zui-biao-zhun-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。