20240226

正则表达式匹配(hot100 hard)

太难想到了，暴力过了2/3左右，粘贴leetcode解析便于复习

思路：动态规划

定义 dp[i][j]表示 s 的前 i 个字符和 p的前 j 个字符能否匹配,分以下几种情况讨论：

1、p[j] 是一个小写字母a-z，则 s[i]必须也为同样的小写字母方能完成匹配

2、p[j] 为'.'，则p[i]与s[j]一定能匹配上，因为p[j]可以与任意字母相等，即dp[i][j] = dp[i - 1][j - 1]

3、p[j] 为'*'，p[j]的前一个字符 p[j−1]匹配任意次(包括 0 次，p[j - 1]为'.'视作匹配)，此时从0开始举几个例子：

(1)匹配0次，则p[j - 1] != s[i]，则p字符串的0到j - 1位与s字符串的0到i位一定不匹配，此时应考虑p字符串的0到j - 2位

位与s字符串的0到i位的匹配性，即dp[i][j] = dp[i][j - 2];

(2)匹配1次，则p[j - 1] = s[i]，p字符串第j - 1到j位一定与s字符串的第i位长度为1的子串匹配（例如a与a*匹配，a*转化为a），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - 1位的匹配性，即dp[i][j] = dp[i - 1][j - 2];

(3)匹配2次，则p[j - 1] = s[i] = s[i - 1]，p字符串第j - 1到j位一定与s字符串第i - 1到i位匹配（例如aa与a*匹配，a*转化为aa），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - 2位的匹配性，即dp[i][j] = dp[i - 2][j - 2];

(4)以此类推，匹配k次，即p[j - 1] = s[i] = s[i - 1] = ... = s[i - k + 1]，则p字符串第j - k + 1到j位一定与s字符串第i - 1到i位匹配（例如aa...a(共k个a)与a*匹配，a*转化为aa...a(共k个a)），那么需判断p字符串第0到j - 2位一定与p字符串第0到i - k位的匹配性，即dp[i][j] = dp[i - k][j - 2]。

图示如下：

优化方法如下：

因此此时dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i] = p[j - 1] || p[j - 1] = '.'))

初始条件：

AC代码：

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            if(p.charAt(i - 1) == '*'){
                dp[0][i] = dp[0][i - 2];
            }
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }else if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i][j - 2] | (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) | p.charAt(j - 2) == '.'));
                }
            }
        }
        return dp[m][n];
    }