题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。示例 1: 输入:s = "()" 输出:true
示例 2: 输入:s = "()[]{}" 输出:true示例 3: 输入:s = "(]" 输出:false
示例 4: 输入:s = "([)]" 输出:false
示例 5: 输入:s = "{[]}" 输出:true
无论是用数组栈,还是容器栈去解决括号匹配的问题,首先,遵循括号匹配的字符串任何一个前缀,其左括号的个数一定是大于等于右括号的个数的。其思路都是先用hash表存储所有类型的括号,左括号为key,右括号为value,遍历括号字符串,如果当前字符为左括号,那么入栈该左括号对应的右括;如果为右括号,将该右括号与栈顶字符比较, 如果不相等或者此时栈为空, 那么肯定括号不匹配,直接返回false。反之相等就出栈该右括号, 如果遍历完字符串后, 栈为空, 那么说明括号是左右相匹配的, 返回true。
数组栈:
class Solution {
public:
bool isValid(string s) {
unordered_map<char,char> pairs = {
{'(',')'},{'{','}'},{'[',']'}
};
char stck[4096];
int top = -1;
for(int i = 0;i < s.length();i++){
if(pairs.find(s[i]) != pairs.end()){ //当前为左括号,入栈右括号
stck[++top] = pairs[s[i]];
}else{
if(top == -1 || stck[top] != s[i]) //当前为右括号不等于栈顶括号,或者栈空
return false;
else //当前为右括号等于栈顶括号,出栈
stck[top--];
}
}
return top == -1; //栈为空返回true
}
};
容器栈:
class Solution {
public:
bool isValid(string s) {
unordered_map<char,char> pairs = {
{'(',')'},{'{','}'},{'[',']'}
};
stack<char> st;
for(int i = 0;i < s.length();i++){
if(pairs.find(s[i]) != pairs.end()){ //当前为左括号,入栈右括号
st.push(pairs[s[i]]);
}else{
if(st.empty() || st.top() != s[i]) //当前为右括号不等于栈顶括号,或者栈空
return false;
else //当前为右括号等于栈顶括号,出栈
st.pop();
}
}
return st.empty(); //栈为空返回true
}
};