hazel'blog
0%

代码随想录第二十九天

发表于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

字符串-有效的括号

题目链接

一开始会想到，左括号的数量和右括号的数量相等，会不会就是有效的括号。其实不然，因为会有[{]}这样的情况出现。仔细分析我们发现，对于有效的括号，它的部分子表达式仍然是有效的括号，比如 {()[()]} 是一个有效的括号，()[{}] 是有效的括号，[()] 也是有效的括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, int>m{{'(',1},{'[',2},{'{',3},
                                {')',4},{']',5},{'}',6}};
        stack<int> st;
        for(char c : s){
            int index = m[c];
            if(index >= 1 && index <= 3){
                st.push(c);
            }
            else if(!st.empty() && m[st.top()] == index-3){
                st.pop();
            }
            else{
                return false;
            }

        }
        return st.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {')':'(',']':'[','}':'{'}
        stack = []
        for i in s:
            if stack and i in dic:
                if stack[-1] == dic[i]: stack.pop()
                else: return False
            else: stack.append(i)
            
        return not stack