栈模拟

一次遍历字符串 sss ， 遇到左括号则入栈，遇到右括号则匹配栈顶。如果右括号匹配成功 ， 栈顶元素弹栈 ， 匹配不成功 ， 则 returnfalsereturn\ \ falsereturn  false 。

提示 : 当遍历完所有字符，记得判断栈内是否为空， 如果空，则有左括号没匹配， returnfalsereturn\ \ falsereturn  false。栈空 returntruereturn\ \ truereturn  true 。

栈

观察 ASCIIASCIIASCII 码值 ， 匹配的左右括号最大相差 222 。 所以用绝对值之差 ≤2\leq 2≤2 判断匹配。

class Solution {
public:bool isValid(string s) {stack stk;for(auto &x:s){if('('==x||'{'==x||'['==x) stk.push(x);else{if(stk.size()&&abs(x-stk.top())<=2) stk.pop();else return false;}}return stk.size()==0;}
};

栈+哈希表

也可以用哈希表，将左括号映射到右括号，判断匹配。

class Solution {
public:bool isValid(string s) {stack stk;unordered_map mp{{'[',']'},{'{','}'},{'(',')'},};for(auto &x:s){if('('==x||'{'==x||'['==x) stk.push(x);else{if(stk.size()&& mp[stk.top()] == x) stk.pop();else return false;}}return stk.empty();}
};

时间复杂度 O(n)O(n)O(n) ， nnn 是字符串 sss 的长度 ， 括号匹配的时间复杂度 O(n)O(n)O(n) 。

空间复杂度 O(n)O(n)O(n) ， 栈的最坏空间复杂度 O(n)O(n)O(n) 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC