有效的括号

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

LeetCode每日一题，20. Valid Parentheses

先看题目描述

大意就是让我们给定一个只包含括号的字符串，让我们判断是不是有效的括号

算法和思路

这题很简单，用一个栈就可以，当是左括号时就进栈，是右括号时就将栈顶元素出栈，若能匹配则继续遍历字符串，若不能匹配则直接返回 false，最终遍历完时根据栈是否为空，来返回 true 或 false

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                stack.push(c);
            } else {
                if (stack.isEmpty() || c != map.get(stack.pop())) return false;
            }
        }
        return stack.isEmpty();
    }
}

后来去看题解，发现可以不使用哈希表来进一步优化时间效率和空间效率，下面是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        return stack.isEmpty();
    }
}

最后去看击败100%的范例，发现别人是用了一个数组来代替栈的作用，第一次见到这种操作，下面是代码

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
class Solution {
    public boolean isValid(String s) {
        int legnth = s.length();
        if ((legnth & 1) == 1) return false;

        char[] stack = new char[legnth + 1];
        stack[0] = ' ';

        int index = 1;
        char[] sChar = s.toCharArray();

        for (char c : sChar) {
            switch (c) {
                case ')' : {
                    if (stack[--index] != '(') return false;
                    break;
                }

                case '}' : {
                    if (stack[--index] != '{') return false;
                    break;
                }

                case ']' : {
                    if (stack[--index] != '[') return false;
                    break;
                }

                default : {
                    stack[index++] = c;
                }
            }
        }

        return index == 1;
    }
}