LeetCode-20-有效的括号

1.我的JAVA暴力解法

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stk=new Stack<Character>();
        int i=0;
        //奇数直接不可能是匹配的
        if(s.length()%2!=0)
            return false;
            
        for (;i<s.length();i++){
            if(s.charAt(i)=='('){
                stk.push('(');
            }
            else if(s.charAt(i)=='{'){
                stk.push('{');
            }
            else if(s.charAt(i)=='['){
                stk.push('[');
            }
            else{
                if(s.charAt(i)==')'){
                    if(!stk.isEmpty()&&stk.peek()=='(')
                        stk.pop();
                    else
                        return false;
                }
                else if (s.charAt(i)=='}'){
                    if(!stk.isEmpty()&&stk.peek()=='{')
                        stk.pop();
                    else
                        return false;
                }
                else if (s.charAt(i)==']'){
                    if(!stk.isEmpty()&&stk.peek()=='[')
                        stk.pop();
                    else
                        return false;
                }
                else{
                    return false;
                }
            }
        }
        return stk.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

2.cpp解法

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2==1){
            return false;
        }
        stack<char> stk;
        for(const auto& ch:s){
            if(ch=='('||ch=='{'||ch=='['){
                stk.push(ch);
            }else if(ch==')'||ch==']'||ch=='}'){
                if(stk.empty()){
                    return false;
                }
                char& c = stk.top();
                if(c=='('&&ch==')'){
                    stk.pop();
                }else if(c=='['&&ch==']'){
                    stk.pop();
                }else if(c=='{'&&ch=='}'){
                    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
20
21
22
23
24
25
26
27
28
29

2.大佬解法,哈希解法

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> list=new LinkedList<>();
        list.add('?');
        if(s.length()%2!=0)
            return false;
        HashMap<Character,Character> map=new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        map.put('?','?');
        int i=0;
        for (;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                list.add(s.charAt(i));
            }else if(map.get(list.pollLast())!=s.charAt(i)){
                return false;
            }
        }
        return list.size()==1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22