LeetCode 10题是“Regular Expression Matching”（正则表达式匹配）。这个问题要求你实现一个支持 . 和 * 的正则表达式匹配功能。

• . 表示任意单个字符。
• * 表示零个或多个前面的字符。

题目描述：

给定一个字符串 s 和一个字符模式 p，实现正则表达式匹配，其中：

• s 可能包含任意字符（除了 * 和 .）。
• p 中的字符可能包含 . 和 *。

你需要实现一个函数来判断 s 是否匹配模式 p。

Java 解法

使用动态规划来解决这个问题是最常见的做法。我们可以使用一个二维数组 dp 来存储中间结果，其中 dp[i][j] 表示 s[0..i-1] 是否与 p[0..j-1] 匹配。

代码实现：

java
复制代码
public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        
        // dp[i][j] 表示 s[0..i-1] 是否与 p[0..j-1] 匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        // 空字符串和空模式是匹配的
        dp[0][0] = true;
        
        // 处理模式 p 中可能出现的 '*'，如果 '*' 之前的字符可以匹配空字符串的话
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];  // 如果 '*' 匹配空字符
            }
        }
        
        // 动态规划填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);
                
                if (pChar == sChar || pChar == '.') {
                    dp[i][j] = dp[i - 1][j - 1];  // 当前字符匹配时，状态转移
                } else if (pChar == '*') {
                    dp[i][j] = dp[i][j - 2]  // '*' 匹配 0 次
                            || (p.charAt(j - 2) == sChar || p.charAt(j - 2) == '.') && dp[i - 1][j];
                    // '*' 匹配 1 次或多次，匹配当前字符
                }
            }
        }
        
        return dp[m][n];
    }
}

代码解析：

1. 初始化：

   • dp[0][0] = true：空字符串与空模式匹配。
   • 通过 dp[0][j] 初始化，处理模式中可能有连续的 *。例如，p = "a*"，这时空字符串和 a* 可以匹配。

2. 动态规划填表：

   • 当模式字符是 . 时，匹配任意字符。
   • 当模式字符是 * 时，分两种情况：
     • * 表示前一个字符出现 0 次，因此看 dp[i][j - 2]。
     • * 表示前一个字符出现 1 次或多次，判断 s[i-1] 与 p[j-2] 是否匹配，如果匹配则看 dp[i-1][j]。

3. 返回结果：

   • 最终返回 dp[m][n]，表示整个字符串 s 是否与整个模式 p 匹配。

时间复杂度：

• 时间复杂度为 O(m * n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。
• 空间复杂度为 O(m * n)，用于存储动态规划表。

示例：

java
复制代码
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("aa", "a*"));  // true
        System.out.println(solution.isMatch("mississippi", "mis*is*p*."));  // false
    }
}

希望这个解法对你有帮助！如果有任何疑问，欢迎继续讨论。