44. 通配符匹配.md

44. 通配符匹配

正则表达式匹配的Java实现分析

这段代码是一个实现正则表达式匹配的Java方法，主要用于判断字符串s是否能被模式串p所匹配，支持.和*两种特殊字符的匹配。实现方式采用动态规划。

初始化变量

• n 和 m：分别表示字符串 s 和模式串 p 的长度。
• 对 s 和 p 前各加一个空格：目的是处理边界情况，简化逻辑。
• ss 和 pp：将处理过的字符串转换为字符数组，方便后续处理。

动态规划数组

• 定义二维数组 boolean[][] f = new boolean[n + 1][m + 1];
• f[i][j] 表示 s 中的前 i 个字符与 p 中的前 j 个字符是否匹配。

初始化条件

• f[0][0] = true; 表示两个空字符串相匹配。

状态转移方程

• 若 p 的第 j 个字符是 '*'：

  1. f[i][j] = f[i][j - 1]：'*' 代表前面的字符出现0次。
  2. f[i][j] = f[i - 1][j]：在 i - 1 >= 0 前提下，'*' 代表前面的字符匹配 s 的前 i-1 个字符。

• 对于非 '*' 字符：

  • f[i][j] = i - 1 >= 0 && f[i - 1][j - 1] && (ss[i] == pp[j] || pp[j] == '.')：需满足三个条件，其中 pp[j] == '.' 表示匹配任何单个字符。

返回结果

• f[n][m] 表示整个字符串 s 是否能被模式串 p 完全匹配。

注意： 存在一个小错误，应使用 . 而非 ? 来匹配任意单个字符。正确的条件应为 (ss[i] == pp[j] || pp[j] == '.')。

class Solution {
    public boolean isMatch(String s, String p) {
        // 分析 如果p[j]是普通字符 那么匹配的条件就是前面的字符匹配,同时s中的第i个字符和p中的第j相同
        // 如果是 . 匹配的条件是前面的字符匹配 .匹配s中的第i个字符
        // 如果是 * 那么如果匹配0个字符 代表 s的前i个字符匹配p的前j - 1个字符
        // * 匹配一个 代表 s 的前i - 1个字符 匹配p的前j - 1个字符


        int n =  s.length();
        int m =  p.length();

        s = " " + s;
        p = " " + p;

        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

        // f(i,j) 代表s中的 1 ~ i 个字符和p中的1 ~ j个字符是否匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;

        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(pp[j] == '*'){
                    f[i][j] = f[i][j - 1] || (i  - 1 >= 0 && f[i - 1][j]);
                }else{
                    f[i][j] = i - 1 >= 0 && f[i - 1][j - 1] && (ss[i] == pp[j] || pp[j] == '?');
                }
            }
        }

        return f[n][m];

    }
}