使用栈数据结构，遍历字符串，若遇到三种左括号，则直接压入栈内。若遇到三种右括号，检查栈顶元素是否为对应的左括号，若不是，说明不匹配，返回 false；若匹配，则将栈顶元素弹出，相当于两个括号匹配一起删除。
遍历字符串后，为了应对类似 "((((((" 的输入，要判断栈是否为空，若不为空说明有的左括号还未被匹配，返回 false
若以上不匹配情况均未发生，说明整个字符串满足匹配关系，返回 true 即可。
代码如下：
class Solution {
public:
bool isValid(string str) {
stack<char> s;
for(char c : str) {
if(c == '(' || c == '{' || c == '[') s.push(c);
else if(c == ')') {
if(!s.empty() && s.top() == '(') s.pop();
else return false;
}
else if(c == ']') {
if(!s.empty() && s.top() == '[') s.pop();
else return false;
}
else if(c == '}') {
if(!s.empty() && s.top() == '{') s.pop();
else return false;
}
}
if(!s.empty()) return false;
return true;
}
};
全部评论
(0) 回帖