Valid Parentheses
文章目录
每日算法——leetcode系列
问题 Valid Parentheses
Difficulty: Easy
Given a string containing just the characters
'(',')','{','}','['and']', determine if the input string is valid.The brackets must close in the correct order,
"()"and"()[]{}"are all valid but"(]"and"([)]"are not.
class Solution {
public:
bool isValid(string s) {
}
};
翻译
验证括符的有效性
难度系数:简单
给定一个只包含字符 '('、 ')'、'{'、 '}'、 '[' 和 ']',判定输入的字符串是否有效。
反括号的位置必须正确, "()" 和 "()[]{}" 是有效的, 但 "(]" 和 "([)]" 不是有效的。
思路
如果做过用栈实现加减法乘除,这题就简单了
括号都分括号和反括号,假设用左表示“([{”,右表示“)]}”区分
遍历字符串,判断字符在左边还是右边:
如果在左边,直接压栈,
-
如有在右边,再分两种情况
如果他和栈顶的字符形成一对括符,表示匹配,弹出栈顶再进行下一个字符判断
不匹配则不能形成完整的括符,结束
代码
class Solution {
public:
bool isValid(string s) {
string left = "([{";
string right = ")]}";
stack<char> charStack;
for (auto ch : s){
if (left.find(ch) != string::npos){
charStack.push(ch);
}else{
if (charStack.empty()){
return false;
}
if (charStack.top() != left[right.find(ch)]){
return false;
}
charStack.pop();
}
}
return charStack.empty();
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论