leetcode算法题-有效的括号

发表于 | 分类于 | 阅读次数: |

题目

本题为leetcode探索初级算法中其它章节的一题

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: “()”
输出: true

示例 2:
输入: “()[]{}”
输出: true

示例 3:
输入: “(]”
输出: false

示例 4:
输入: “([)]”
输出: false

示例 5:
输入: “{[]}”
输出: true

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解法

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
class Solution {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if(aChar == '(' || aChar == '{' || aChar == '['){
                stack.push(aChar);
            }
            if(aChar == ']'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('[')){
                    return false;
                }
            }
            if( aChar == '}'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('{')){
                    return false;
                }
            }
            if(aChar == ')'){
                if(stack.isEmpty()){
                    return false;
                }
                Character pop = stack.pop();
                if(pop == null || !pop.equals('(')){
                    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
22
23
24
25
26
public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

时间复杂度：O(n)O(n)，其中 nn 是字符串 ss 的长度。

空间复杂度：O(n + |\Sigma|)O(n+∣Σ∣)，其中 \SigmaΣ 表示字符集，本题中字符串只包含 66 种括号，|\Sigma| = 6∣Σ∣=6。栈中的字符数量为 O(n)O(n)，而哈希映射使用的空间为 O(|\Sigma|)O(∣Σ∣)，相加即可得到总空间复杂度。

与官方相比大致思路相同，官方中先判断了长度，题目中前提是“只包括”所以长度为奇数肯定是false。
另外用到了map简化了if-else判断。