【Leetcode合集】20. 有效的括号

20. 有效的括号

20. 有效的括号

代码仓库地址： https://github.com/slience-me/Leetcode

个人博客 ：https://slienceme.xyz

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

方案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：初次优化

优化代码结构

class Solution {
public:bool isValid(string s) {stack<char> parentheses;unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};for (char c : s) {if (c == '(' || c == '[' || c == '{') {parentheses.push(c);} else {// 栈为空或者栈顶与当前括号不对应if (parentheses.empty() || parentheses.top() != mapping[c]) {return false;}parentheses.pop();}}return parentheses.empty();}
};

执行用时分布 4ms 击败35.12%使用 C++ 的用户

消耗内存分布6.57MB 击败19.98%使用 C++ 的用户

方案3：再优化

特殊情况立即截断

class Solution {
public:bool isValid(string s) {// 奇数直接截断if (s.length() % 2 == 1) {return false;}stack<char> parentheses;unordered_map<char, char> mapping = {{')', '('},{']', '['},{'}', '{'}};int leftSum = 0;for (char c: s) {// 左括号数量>总括号的一半 立即截断if (leftSum>(s.length()/2)){return false;}if (c == '(' || c == '[' || c == '{') {parentheses.push(c);leftSum++;} else {// 栈为空或者栈顶与当前括号不对应if (parentheses.empty() || parentheses.top() != mapping[c]) {return false;}parentheses.pop();}}return parentheses.empty();}
};

执行用时分布 0ms 击败100%使用 C++ 的用户

消耗内存分布6.72MB 击败7.68%使用 C++ 的用户