题目描述
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
解法一:stack
这道题目是典型的堆栈数据结构的应用,虽然思路很清晰,代码也很简单,但是要注意逻辑的严谨性。尤其是在判断 栈顶元素是否匹配之前,要先判断栈是否为空。
class Solution {
public:
bool isValid(const std::string& s) {
std::stack<char> st;
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
if (c == '}' && st.top() != '{') return false;
if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}
};
评论