动态规划，滚动数组优化空间复杂度

动态规划

设f[i,j]代表str[0-i]是否匹配pattern[0-j]
状态转移方程为

注意条件的等号代表两字符匹配，如'.'与'a'匹配，'a'与'a'匹配。
还要注意s[i]对应的实际上时str[i-1],p[j]对应的时partten[j-1]

解释一下：

1. 当p[i]!=*时，为常规情况，显然只有s[i]==p[i]且s[0...i-1]匹配p[0...j-1] (即f[i-1,j-1]==true) 时s[0...i]才与p[0...j]匹配；否则一定不匹配。从而到处第一个递推公式。

2. 当p[i]==*时，
   若s[i]==p[j-1]（星号的前缀），要想匹配有两种可能：

   • s[i]不作为星号的匹配，即*的长度取0，此时显然只有s[0...i]匹配p[0...j-2]时才能匹配，即f[i,j-2]==true;
   • s[i]作为星号的匹配，此时需要s[0...i-1]匹配p[0...j] 即f[i-1,j];
   • 两者有一种情况成立即可，所以需取或。

   若s[i]!=p[j-1]，那么显然只有不匹配星号这一种情况，即f[i,j-2]=true时匹配
   这样我们就得到了第二个式子。

初始化的问题

f[0,0]=true;
p[j]=='*'时,f[0,j]=f[0,j-2];
否则f[0,j]=false;

代码：

public class Solution {
    public boolean judge(char a,char b){
        if(a=='.')return true;
        else return a==b;
    }
    public boolean match(char[] str, char[] pattern)
    {
        int m=pattern.length;int n=str.length;
        boolean[][] dp=new boolean[n+1][m+1];
        //初始化
        dp[0][0]=true;
        for(int j=1;j<=m;j++){
            if(pattern[j-1]=='*')dp[0][j]=dp[0][j-2];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(pattern[j-1]!='*'){
                    if(judge(pattern[j-1],str[i-1]))
                        dp[i][j]=dp[i-1][j-1];
                }
                else{
                    if(judge(pattern[j-2],str[i-1]))
                        dp[i][j]=dp[i][j-2]|dp[i-1][j];
                    else dp[i][j]=dp[i][j-2];
                }
            }
        }
        return dp[n][m];
    }
}

还采用滚动数组优化空间复杂度，代码如下

public class Solution {
    public boolean judge(char a,char b){
        if(a=='.')return true;
        else return a==b;
    }
    public boolean match(char[] str, char[] pattern)
    {
        int m=pattern.length;int n=str.length;
        //滚动数组优化
        int cur=0,pre=1;
        boolean[][] dp=new boolean[2][m+1];
        //初始化
        dp[cur][0]=true;
        for(int j=1;j<=m;j++){
            if(pattern[j-1]=='*')dp[cur][j]=dp[cur][j-2];
        }
        for(int i=1;i<=n;i++){
            cur=1-cur;pre=1-pre;//滚动
            for(int j=1;j<=m;j++){
                if(pattern[j-1]!='*'){
                    if(judge(pattern[j-1],str[i-1]))
                        dp[cur][j]=dp[pre][j-1];
                    else dp[cur][j]=false;
                }
                else{
                    if(judge(pattern[j-2],str[i-1]))
                        dp[cur][j]=dp[cur][j-2]|dp[pre][j];
                    else dp[cur][j]=dp[cur][j-2];
                }
            }
        }
        return dp[cur][m];
    }
}