20. 有效的括号

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

示例 4：

1
2
输入：s = "([)]"
输出：false

示例 5：

1
2
输入：s = "{[]}"
输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

题解：

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
public boolean isValid(String s) {
    //如果字符串的长度为奇数，则可以直接返回false
    int n = s.length();
    if (n % 2 == 1) {
        return false;
    }

    Stack<Character> stack = new Stack<>();

    //使用哈希表存储括号之间的对应关系
    HashMap<Character, Character> map = new HashMap<>();

    map.put('}', '{');
    map.put(')', '(');
    map.put(']', '[');

    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);

        //是左括号，进栈
        if (map.containsValue(c)) {
            stack.push(c);
        } else {
            //是右括号，判断栈是否为空，若不为空弹出栈顶元素，比较看是否为对应的左括号
            /*
             * Stack.peek()和Stack.pop(）的相同点是 获取栈顶的值，
             * 不同点 则是 Stack.peek()只是获取栈顶的值，而Stack.pop()是获取栈顶的值然后删除。*/
            if (stack.isEmpty() || stack.peek() != map.get(c)) {
                return false;
            }

            //满足条件，弹出元素
            stack.pop();

        }

    }
    //存在全是左括号的情况，最终栈为空则返回true，栈中还有元素返回false
    return stack.isEmpty();
}
  • 时间复杂度：O(N)，正确情况下需要遍历整个完整的字符串
  • 空间复杂度：O(N + 6),6代表6种括号。