力扣(LeetCode)20. 有效的括号(C++)

栈模拟

一次遍历字符串 $s$ ， 遇到左括号则入栈，遇到右括号则匹配栈顶。如果右括号匹配成功 ， 栈顶元素弹栈 ， 匹配不成功 ， 则 $returnfalse$ 。

提示 : 当遍历完所有字符，记得判断栈内是否为空， 如果空，则有左括号没匹配， $returnfalse$。栈空 $returntrue$ 。

栈

观察 $ASCII$ 码值 ， 匹配的左右括号最大相差 $2$ 。 所以用绝对值之差 $\le 2$ 判断匹配。

class Solution {
public:
    bool isValid(string s) {
        stack<char> 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

栈+哈希表

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

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char,char> 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();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

博主致语

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

AC