链接: link
这道题呢就非常适合用栈来搞:
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s。 定义一个栈,然后我们只需去遍历这个字符串: 如果遇到左括号,就给它入栈;如果遇到右括号,就取栈顶元素与之进行匹配(同时pop掉栈顶元素) 举个例子
遍历括号字符串,前三个都是左括号,入栈 再往后是一个右括号,那就pop掉栈顶的左括号与之匹配
匹配成功,继续往后遍历 再往后还是右括号,再去取栈顶元素匹配
匹配成功; 接着再往后是左括号,入栈
再往后,右括号,取栈顶匹配
匹配成功; 再往后,还是右括号,取栈顶元素匹配
匹配成功,至此字符串遍历结束,全部匹配成功。
但是,上面是匹配成功的情况,那哪些情况会匹配失败呢?
有三种情况:
class Solution {
public:
bool isValid(string& s) {
stack<char> st;
for(auto e:s)
{
//如果是左括号就入栈
if(e=='['||e=='{'||e=='(')
st.push(e);
//如果是右括号就获取栈顶元素与之匹配
else if(e==']'||e==')'||e=='}')
{
//此时若栈为空,则没有左括号去匹配
if(st.empty())
return false;
char top=st.top();
st.pop();
//左右括号不匹配
if((e==']'&&top!='[')
||(e==')'&&top!='(')
||e=='}'&&top!='{')
return false;
}
}
//匹配完所有的右括号之后栈不为空
return st.empty();
}
};