19.正则表达式匹配

参考链接

牛客网-剑指Offer

帅地

LeetCode LCR 137.模糊搜索验证

优秀题解

class Solution {
    public boolean isMatch(String A, String B) {
        int n = A.length();
        int m = B.length();
        boolean[][] f = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                //分成空正则和非空正则两种
                if (j == 0) {
                    f[i][j] = i == 0;
                } else {
                    //非空正则分为两种情况 * 和 非*
                    if (B.charAt(j - 1) != '*') {
                        if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {
                            f[i][j] = f[i - 1][j - 1];
                        }
                    } else {
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if (j >= 2) {
                            f[i][j] |= f[i][j - 2];
                        }
                        //看
                        if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {
                            f[i][j] |= f[i - 1][j];
                        }
                    }
                }
            }
        }
        return f[n][m];
    }
}

作者：Jerry
链接：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/92888/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

对题解的个人理解： 使用字符串A中的每个字符 与 字符串B 中的每个字符 一一匹配

A: "aaaab", B: "a*b"

f(i, j)	0(B==null)	1('a')	2('*')	3('b')
0(A==null)	true		true
1('a')		true	true
2('a')			true
3('a')			true
4('a')			true
5('b')				true

A: "aaa", B: "ab*aa"

f(i, j)	0(B==null)	1('a')	2('b')	3('*')	4('a')	5('a')
0(A==null)	true
1('a')		true		true
2('a')					true
3('a')						true

(0, 0)--(1, 1)--(1, 3)--(2, 4)--(3, 5)