20. 有效的括号
代码仓库地址： https://github.com/slience-me/Leetcode
个人博客 ：https://slienceme.xyz
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
方案1：暴力解
第一种纯暴力解
class Solution {
public:
bool isValid1(string s) {
stack<char> st_char;
for (const auto &item: s){
if (item=='(' || item=='[' || item=='{'){
st_char.push(item);
} else {
if(!st_char.empty()){
char temp = st_char.top();
st_char.pop();
if (!item) {
return false;
} else if (item==')' && temp!='('){
return false;
} else if(item==']' && temp!='['){
return false;
}else if(item=='}' && temp!='{'){
return false;
}
} else {
return false;
}
}
}
if (st_char.empty()){
return true;
} else {
return false;
}
}
};
执行用时分布 4ms 击败35.12%使用 C++ 的用户
消耗内存分布6.47MB 击败57.33%使用 C++ 的用户
方案2：初次优化
优化代码结构
执行用时分布 4ms 击败35.12%使用 C++ 的用户
消耗内存分布6.57MB 击败19.98%使用 C++ 的用户
方案3：再优化
特殊情况立即截断
执行用时分布 0ms 击败100%使用 C++ 的用户
消耗内存分布6.72MB 击败7.68%使用 C++ 的用户
备注：由于有的代码与编辑器冲突，所以改为图片，源代码见github
文档信息
- 本文作者：slience_me
- 本文链接：https://slienceme.xyz/2023/11/25/Leetcode_20/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）