剑指 Offer 19. 正则表达式匹配

crazyjums

LeetCode刷题动态规划hard

发布于：Nov 23, 2020

次浏览

剑指 Offer 19. 正则表达式匹配

https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

1 题目

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:

输入:
s = “ab”
p = “.“
输出: true
解释: “.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。
示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:

输入:
s = “mississippi”
p = “misisp*.”
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。
注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 分析

使用正则表达式进行求解。将两个字符串从后往前进行比较，其中模式串的最后一个字符可能由一下三种情况：

正常字符（[a-zA-Z]）
星号（*）
点号（.）

定义主串为$s$，长度为$m$，模式串为$p$，长度为$n$。则有一下三种情况：

$p[n - 1]$为一个正常字符，则此时只能将模式串的最后一个字符和主串的最后一个字符进行比较，如果模式串的最后一个字符等于主串的最后一个字符（$p[n - 1] == s[m-1]$），则继续判断$p[n-2]$是否等于$s[m-2]$，以此类推。
$p[n-1]==’.’$。因为题目中说，$’.’$可以匹配任何一个字符，所以模式串和主串的最后一个就相当于匹配上了，继续匹配$p[n-2]$和$s[m-2]$。
$p[n-1]==’‘$。题目中说$’‘$可以匹配$’*’$号之前的那个字符任意多次（包括0次），假设$p[n-2]==c$，则主串中的字符可以匹配$c$0次或者多次：
1. 匹配0次。那么模式串的最后两个字符就可以不用看了，因为主串被匹配了0次。比如：$s=”abc”$，$p=”abcd*”$，可将$p$的倒数第二个字符$d$认为匹配了0次，所以主串和模式串可以匹配。
2. 匹配了多次。此种情况必须满足$s[m-1]==c$或者$c=’.’$，否则将不能匹配多次。比如：$s=”abc”$，$p=”abc*”$，可以认为字符$’c’$匹配了1次；或者$s=”abc”$，$p=”ab.*”$，此时两个串也可以匹配上。

上面将所有的可能情况都列举了，那么此时只需要定义一个$dp$数组即可，其中$dp[i][j]$表示$s$串的前$i$个字符和$p$串的前$j$个字符能否匹配。此时又分成以下4中情况：

主串为空，模式串也为空，那么此时一定可以匹配
主串为空，模式串不为空，此时不能直接得出结果，必须通过计算得出，比如$s=””$，$p=”abc*”$，此种情况两个串可以匹配。
主串不为空，模式串为空，此时一定不能匹配。
主串不为空，模式串也不为空，那么此时就需要计算得出结果

3 代码

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        /*
        定义dp数组，dp[i][j]表示s串的前i个字符和p串的前j个字符是否匹配
        有一下四种情况：
            1. 主串为空， 模式串也为空， 此种情况可以匹配
            2. 主串为空， 模式串为非空， 此种情况不能直接判断是否能匹配，需要计算
            3. 主串非空， 模式为空， 此时一定不能匹配
            4. 主串和模式串都是非空， 此时需要计算
                计算规则如下：从后往前匹配，可以将一个大的问题转化为一个子问题
                模式串的最后一个字符有三种可能：正常字符，星号（*），点（.）
                1. 如果p的最后一个字符是正常字符，则判断：
                    - p[n - 1] == s[m - 1]，则继续匹配s和p的倒数第二个字符 dp[i][j] = dp[i - 1][j - 1]
                    - p[n - 1] != s[m - 1]，则说明最后一个字符不匹配 dp[i][j] = false
                2. 如果p的最后一个字符是"."，说明可以匹配任何字符，此时继续匹配倒数第二个字符  dp[i][j] = dp[i - 1][j - 1]
                3. 如果p的最后一个字符是“*”，表示“*”之前的一个字符（p[n - 1] = c）可以出现0次或多次，
                    - 出现0次：即表示p串的最后两个字符可以不用比较，直接比较s[n - 1]和p[n - 3]，dp[i][j] = dp[i][j - 2]
                    - 出现多次：此种情况下，要求s[m - 1] == p[n- 1] || p[n - 1] == '.'，模式串不动，主串继续向前移动。
                     dp[i][j] = [i - 1][j]
        
        */
        dp[0][0] = true;
        // for (int i = 1; i < n; i++) {
        //     dp[0][i] = false;
        // }

        for (int i = 0; i <= m; i++) //主串
            for (int j = 0; j <= n; j++) { //模式匹配串
                //如果模式串是空串
                //1.主串为空， 模式串也为空， 此种情况可以匹配
                //2.主串非空， 模式为空， 此时一定不能匹配
                if (j == 0) {
                    dp[i][j] = i == 0;
                } else {
                    // char ch = p.charAt(j - 1);
                    if (p.charAt(j - 1) != '*') { //将正常字符和“.”合并处理
                        if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    } else {
                        //出现0次
                        if (j >= 2) {
                            dp[i][j] = dp[i][j - 2];
                        } 
                        //出现多次
                        /*
                        关于为什么用|=，比如这段代码： //碰到 * 了，
                        分为看和不看两种情况 //不看 if (j >= 2) { f[i][j] |= f[i][j - 2]; 
                        //可用可不用，因为dp矩阵初始化默认为false，本质上和=一样 } 
                        //看 if (i >= 1 && j >= 2 
                        && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) { f[i][j] |= f[i - 1][j]; 
                        //必须使用，否则不能ac }

                        其中，第一步先算的是不看‘*’的情况，然后第二步再算看‘*’的情况。
                        也就是说，对于f[i][j]我们会算两次。如果在第一次，即不看'*'的时候，
                        就已经算出来TURE了。那在第二步看'*'的时候。不管结果是ture还是false，
                        都保持true不变，这是合理的，因为只要其中有一种情况能完整匹配，结果就为true。
                        这就是为什么要用或符号。 这个不难证明，举个例子 "ba" "baa*" 这种情况下直接用=号过不了。
                        */
                        if (i >=1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
                
            }

        return dp[m][n];
    }
}