要求

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

有效字符串需满足：

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

左括号必须以正确的顺序闭合，情况反映在示例四，这种情况返回 false 。我一开始就是没有留意这个情况。

原题：有效的括号

示例

示例 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

思路

最先想到的思路就是既然括号需要正确的顺序闭合，那就直接替换，替换完成以后如果字符串的长度为 0，就说明括号都是有效的

1
2
3
s=s.replace("()", "");
s=s.replace("{}", "");
s=s.replace("[]", "");

因为存在 s = "{[]}" 的情况，这种情况下必须里面的 方括号[] 完成替换后，才能替换外面的 花括号{} ，所以就需要用到循环

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 boolean isValid(String s) {
        // 先排除奇数长度的情况
        if (s.length() % 2 != 0) {
            return false;
        }
        // 遍历
        while (true) {
            // 每一轮替换开始前的长度
            int startLength = s.length();
            s=s.replace("()", "");
            s=s.replace("{}", "");
            s=s.replace("[]", "");
            // 每一轮替换结束后的长度
            int endLength = s.length();
            // 结束循环的条件：替换前后相等，说明没有可以替换的了
            if (startLength == endLength) {
                return endLength == 0;
            }
        }
    }
}

但是效率太低了

执行用时：44 ms, 在所有 Java 提交中击败了 5.87%的用户

内存消耗：41.7 MB, 在所有 Java 提交中击败了 5.01%的用户

解决

遍历给定的字符串 s 时，当遇到一个左括号，我们会期望在后续的遍历中，遇到一个最近的相同类型的右括号将其闭合。

而栈这种数据结构的特点就是先入后出。即遇到左括号入栈，如果括号有效的话，下一个遇到的右括号肯定是与栈顶的左括号对应，此时栈顶的左括号出栈，遍历完所有括号后 stack 为空。

当然为了考虑通用性，这里还是用 map 集合来实现左右括号的对应

1
2
3
4
5
6
7
8
9
10
// 使用匿名内部类方法赋值
// 第一层括弧实际是定义了一个匿名内部类
// 第二层括弧实际上是一个实例初始化块，这个块在内部匿名类构造时被执行。
new HashMap<Character, Character>(){
    {
        put('(', ')');
        put('{', '}');
        put('[', ']');
    }
};

完整代码

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
class Solution {
    public boolean isValid(String s) {
        // 先排除奇数长度的情况
        if (s.length() % 2 != 0) {
            return false;
        }
        // 使用匿名内部类方法赋值
        HashMap<Character, Character> map = new HashMap<Character, Character>() {
            {
                put('(', ')');
                put('{', '}');
                put('[', ']');
            }
        };
        //创建栈
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            // 左括号要入栈
            if (map.containsKey(ch)) {
                stack.push(ch);
              // 不是左括号的情况，栈顶元素出栈看看是否匹配
              // 这样判断的逻辑：比如：s="()"，那么")"在pop()出栈后，栈为空
            } else if (stack.empty() || map.get(stack.pop()) != ch) {
                return false;
            }
        }
        // 遍历完所有括号后判断栈是否为空
        return stack.isEmpty();
    }
}