【LeetCode】Day126-正则表达式匹配

题目

10. 正则表达式匹配【困难】

题解

用字符串匹配纠结了半天，结果解法是用动态规划，果然还是我太天真了

对于 p 中一个字符而言，它只能在 s 中匹配一个字符，匹配的方法具有唯一性；而对于 p 中字符 + 星号的组合而言，它可以在 s 中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

官解说的云里雾里，个人感觉这篇题解「手画图解」动态规划，需要仔细的分情况讨论说的特别好，有图，分析也比较细致

1. 状态定义：dp[i][j] 表示s[0…i-1]与p[0…j-1]是否能够匹配。

2. 状态转移方程：本题最复杂的地方，关键是对于星号的讨论，p[j-1]星号可以让p[j-2]在s串中消失、重复一次、重复>=2次
   

3. 初始条件：dp[0][0]=true，表示两个空字符串可以匹配上

4. 返回值：dp[m][n]

class Solution {
    public boolean isMatch(String s, String p) {
        int m=s.length(),n=p.length();
        boolean[][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i][j-2];//无论p[j-2]是啥,都能被*消掉,因此dp[i][j]和dp[i][j-2]值相等
                    //若s[i-1]和p[j-2]匹配上,说明s[i-1]重复了多次
                    if(match(s,p,i,j-1)){
                        dp[i][j]=dp[i-1][j] || dp[i][j-2];
                    }
                }
                else{
                    //两个字母匹配上了或者和"."匹配上了
                    if(match(s,p,i,j)){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }
    public boolean match(String s,String p,int i,int j){
        if(i==0)
            return false;
        if(p.charAt(j-1)=='.')
            return true;
        return s.charAt(i-1)==p.charAt(j-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度：$O(mn)$

空间复杂度：$O(mn)$