系列文章目录
发现一篇一篇放在这里,编辑的时候很浪费时间,干脆把专栏的链接放在这里,如果需要,直接去专栏里面看即可,nice!
文章目录
前言
每天进步一点点哟!
一、背景
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
二、我的思路
这个还是比较简单的,之前做过数学表达式求解的,这个相比就是弟弟。
采用栈的数据结构,将所有的左括号入栈,当访问到右括号的时候,那么就和栈顶元素进行比较,如果匹配,那么栈顶元素出栈,再继续匹配下一个字符;如果不匹配,那么直接返回false.
代码如下:
class Solution {
public:
bool isValid(string s) {
stack <char> bracket_match;
for(char c:s)
{
if(c=='('||c=='['||c=='{')
{
bracket_match.push(c);
}
else
{
//右括号,但是栈是空的,必然false
if (bracket_match.empty())
return false;
else
{
if(c==')'&&bracket_match.top()=='(') bracket_match.pop();
else if (c==']'&&bracket_match.top()=='[') bracket_match.pop();
else if (c=='}'&&bracket_match.top()=='{') bracket_match.pop();
else return false;
}
}
}
if(bracket_match.empty()) return true;
return false;
}
};
这个代码速度有点慢,4ms,有网友是0ms的,我也不晓得具体是怎么优化的。
二、官方的思路
官方给的答案思路比我多一个点,就是我是用if_else语句判断括号匹配与否,它是直接使用map数组。
代码如下:
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
来源:力扣(LeetCode)
总结
这个基本上就是说方法是比较一致的,当然有人用C语言写这个,他是用的数组去存的,再是左右括号的ASCII码值相差1(具体多少忘记了),做减法可以判断括号是否匹配,也能达到目的。其实数组的话只需记录最后存进去的那个字符的下标即可,一样的道理。
喜欢就点个赞叭!!!