有效的括号匹配：五种 Java 实现方案详解

3. 算法设计与实现

3.1 标准栈解法

核心思想：

使用栈数据结构，遍历字符串，遇到左括号入栈，遇到右括号检查栈顶是否匹配，最后检查栈是否为空。

算法思路：

1. 初始化一个空栈
2. 遍历字符串中的每个字符：
   • 如果是左括号（'(', '[', '{'），将其压入栈中
   • 如果是右括号（')', ']', '}'）：
     • 如果栈为空，返回 false（没有对应的左括号）
     • 弹出栈顶元素，检查是否与当前右括号匹配
     • 如果不匹配，返回 false
3. 遍历结束后，如果栈为空，返回 true；否则返回 false（有未匹配的左括号）

Java 代码实现：

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        // 使用 Java 内置的 Stack 类
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            // 如果是左括号，压入栈中
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // 如果是右括号
            else {
                // 如果栈为空，说明没有对应的左括号
                if (stack.isEmpty()) {
                    return false;
                }
                // 弹出栈顶元素并检查是否匹配
                char top = stack.pop();
                if (!isMatchingPair(top, c)) {
                    return false;
                }
            }
        }
        // 最后检查栈是否为空
        return stack.isEmpty();
    }

    // 辅助方法：检查两个括号是否匹配
    private boolean isMatchingPair(char left, char right) {
        return (left == '(' && right == ')') ||
               (left == '[' && right == ']') ||
               (left == '{' && right == '}');
    }
}

性能分析：

• 时间复杂度：O(n)，其中 n 是字符串长度，每个字符处理一次
• 空间复杂度：O(n)，最坏情况下栈中可能存储所有左括号
• 优点：思路清晰，易于理解和实现
• 缺点：使用 Java 的 Stack 类有一定开销

3.2 使用数组模拟栈

核心思想：

使用数组和指针模拟栈操作，避免 Stack 类的开销，提高性能。

算法思路：

1. 使用字符数组作为栈，使用一个整数指针表示栈顶
2. 遍历字符串，与解法一类似，但直接操作数组
3. 注意数组大小的选择（最大为字符串长度）

Java 代码实现：

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        // 如果长度为奇数，一定无效
        if (n % 2 == 1) {
            return false;
        }
        // 使用数组模拟栈
        char[] stack = new char[n];
        int top = -1; // 栈顶指针
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                // 入栈
                stack[++top] = c;
            } else {
                // 如果栈为空，返回 false
                if (top == -1) {
                    return false;
                }
                // 检查栈顶元素是否匹配
                char left = stack[top--];
                if (!isMatch(left, c)) {
                    return false;
                }
            }
        }
        // 栈应该为空
        return top == -1;
    }

    private boolean isMatch(char left, char right) {
        return (left == '(' && right == ')') ||
               (left == '[' && right == ']') ||
               (left == '{' && right == '}');
    }
}

性能分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)，但避免了 Stack 类的额外开销
• 优点：性能更好，内存使用更高效
• 缺点：需要手动管理栈指针

3.3 使用 HashMap 存储映射

核心思想：

使用 HashMap 存储右括号到左括号的映射，代码更简洁，易于扩展。

算法思路：

1. 创建 HashMap，将右括号映射到对应的左括号
2. 遍历字符串：
   • 如果是左括号，入栈
   • 如果是右括号，检查栈顶是否等于该右括号对应的左括号
3. 最后检查栈是否为空

Java 代码实现：

import java.util.Stack;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        // 创建括号映射
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            // 如果是右括号
            if (map.containsKey(c)) {
                // 获取栈顶元素，如果栈为空则使用特殊字符
                char top = stack.isEmpty() ? '#' : stack.pop();
                // 检查是否匹配
                if (top != map.get(c)) {
                    return false;
                }
            }
            // 如果是左括号
            else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

性能分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n) + O(1)（HashMap 的空间）
• 优点：代码简洁，易于扩展新的括号类型
• 缺点：HashMap 有一定的内存开销

3.4 早期优化与剪枝

核心思想：

在开始处理前进行一些快速检查，提前排除无效情况，提高平均性能。

算法思路：

1. 检查字符串长度是否为奇数，如果是则直接返回 false
2. 检查第一个字符是否为右括号，如果是则直接返回 false
3. 检查最后一个字符是否为左括号，如果是则直接返回 false
4. 使用数组模拟栈进行常规检查

Java 代码实现：

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        // 快速失败检查
        if (n % 2 == 1) return false;
        if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}') return false;
        if (s.charAt(n - 1) == '(' || s.charAt(n - 1) == '[' || s.charAt(n - 1) == '{') return false;

        // 数组模拟栈
        char[] stack = new char[n];
        int top = -1;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack[++top] = c;
            } else {
                if (top == -1) return false;
                char left = stack[top--];
                if (!isPair(left, c)) return false;
            }
        }
        return top == -1;
    }

    private boolean isPair(char left, char right) {
        return (left == '(' && right == ')') ||
               (left == '[' && right == ']') ||
               (left == '{' && right == '}');
    }
}

性能分析：

• 时间复杂度：O(n)，但平均情况下可能更早结束
• 空间复杂度：O(n)
• 优点：平均性能更好，快速排除明显无效的情况
• 缺点：增加了额外的检查，代码稍复杂

3.5 递归消除法

核心思想：

递归地消除匹配的括号对，类似于消消乐。每次找到最内层的匹配括号对并消除，直到字符串为空或无法消除。

算法思路：

1. 使用递归函数处理字符串
2. 如果字符串为空，返回 true
3. 查找并消除最内层的匹配括号对
4. 如果没有找到匹配对，返回 false
5. 递归处理消除后的字符串

Java 代码实现：

class Solution {
    public boolean isValid(String s) {
        // 递归终止条件
        if (s.isEmpty()) {
            return true;
        }
        // 查找匹配的括号对并消除
        String reduced = reducePairs(s);
        // 如果没有消除任何括号，说明无效
        if (reduced.equals(s)) {
            return false;
        }
        // 递归处理
        return isValid(reduced);
    }

    // 消除最内层的匹配括号对
    private String reducePairs(String s) {
        // 查找并替换所有匹配的括号对
        String result = s.replace("()", "").replace("[]", "").replace("{}", "");
        return result;
    }
}

性能分析：

• 时间复杂度：最坏情况 O(n²)，因为每次替换需要遍历字符串
• 空间复杂度：O(n) 递归调用栈深度
• 优点：思路独特，不使用栈
• 缺点：效率较低，不适用于长字符串

4. 性能对比

4.1 复杂度对比表

4.2 实际性能测试

测试环境：JDK 17，字符串长度 10000，随机生成有效括号序列，运行 10000 次取平均值

4.3 各场景适用性分析

1. 面试场景：推荐标准栈解法或 HashMap 映射法，代码清晰，易于解释
2. 竞赛场景：推荐数组模拟栈，性能最优
3. 生产环境：推荐早期优化法，兼顾性能和健壮性
4. 练习场景：推荐递归消除法，展示不同思路
5. 扩展场景：如果需要支持新的括号类型，推荐 HashMap 映射法

5. 扩展与变体

5.1 包含其他字符的括号匹配

题目描述：给定一个包含括号和其他字符的字符串，判断其中的括号是否匹配。

Java 代码实现：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            // 只处理括号字符
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (!isMatching(top, c)) return false;
            }
            // 其他字符忽略
        }
        return stack.isEmpty();
    }

    private boolean isMatching(char left, char right) {
        return (left == '(' && right == ')') ||
               (left == '[' && right == ']') ||
               (left == '{' && right == '}');
    }
}

5.2 最长有效括号子串

题目描述：给定一个只包含 '(' 和 ')' 的字符串，找出最长有效括号子串的长度。

Java 代码实现：

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        // 使用栈存储索引
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 哨兵节点
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i); // 新的起点
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

5.3 生成所有有效的括号组合

题目描述：给定 n 对括号，生成所有可能的有效括号组合。

Java 代码实现：

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String current, int open, int close, int max) {
        // 如果当前字符串长度达到 2n，添加到结果
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        // 可以添加左括号的条件：左括号数量小于 n
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        // 可以添加右括号的条件：右括号数量小于左括号数量
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

5.4 检查括号的嵌套深度

题目描述：给定一个有效括号字符串，返回该字符串的嵌套深度。

Java 代码实现：

class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0;
        int currentDepth = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                currentDepth++;
                maxDepth = Math.max(maxDepth, currentDepth);
            } else if (c == ')') {
                currentDepth--;
            }
        }
        return maxDepth;
    }
}

6. 总结

6.1 核心思想总结

1. 栈的 LIFO 特性：括号匹配问题天然适合使用栈解决，后出现的左括号需要先匹配
2. 映射关系：右括号与左括号存在固定的一一对应关系
3. 遍历检查：一次遍历即可完成检查，时间复杂度 O(n)
4. 边界处理：需要仔细处理空栈、字符串边界等情况
5. 多种实现：可以使用不同的数据结构实现栈，各有优劣

6.2 实际应用场景

1. 编译器设计：语法分析中的括号匹配检查
2. 表达式求值：算术表达式、逻辑表达式的括号验证
3. 代码编辑器：实时检查代码中的括号匹配
4. 配置文件解析：JSON、XML 等格式的括号匹配验证
5. 游戏开发：某些游戏中的路径或操作序列验证

6.3 面试建议

1. 掌握标准解法：必须熟练掌握使用栈的标准解法
2. 理解原理：能够解释为什么栈适合解决这个问题
3. 边界测试：准备测试用例：空字符串、单字符、有效/无效序列、嵌套深度大等
4. 代码简洁：尽量写出简洁、清晰的代码
5. 扩展思考：了解相关变体问题，展示知识广度

6.4 常见面试问题 Q&A

Q1：为什么使用栈而不是其他数据结构？
A1：因为括号匹配需要'后进先出'的特性，最后出现的左括号需要最先匹配，这与栈的 LIFO 特性完全吻合。

Q2：如果括号类型增加到 10 种，如何修改代码？
A2：如果使用 HashMap 存储映射关系，只需要在 HashMap 中添加新的映射即可，代码基本不需要修改。如果使用硬编码判断，需要修改判断逻辑。

Q3：如何处理包含其他字符的字符串？
A3：遍历时忽略非括号字符，只处理括号字符，其他逻辑不变。

Q4：这个算法能否并行化？
A4：由于括号匹配具有顺序依赖，难以直接并行化。但可以将字符串分段，每段独立检查局部有效性，然后合并检查段间匹配，实现较为复杂。

Q5：如果字符串非常大（超过内存限制），如何处理？
A5：可以使用流式处理，逐字符读取并维护栈状态。由于栈大小最多为字符串长度的一半，如果括号深度很大，仍然可能内存不足，但这种情况较少见。