本文共 2465 字，大约阅读时间需要 8 分钟。

dp解法，时间复杂度O(NNM)，空间复杂度O(N*M)

dp[i][j] 表示 str[i…La] 和 pattern[j…Lb] 是否通配

动态规划，从后向前推

第一，dp[La][Lb]一定为真,两个空串 第二，处理dp[i][Lb]部分，表示pattern已经结束，str没有结束，所以全部为假 第三，处理dp[La][j]部分，表示str已经结束，pattern没有结束，所以当pattern结尾都是X* 才会为真 第四，处理dp[i][Lb-1]部分，由于* 的存在，所以此部分需要特殊处理，表示pattern只剩最后一个字符，str没有结束，只有dp[La][Lb]有可能为真，其他都为假。 第五，打表dp[i][j],其中当pattern[j]==’*’,所有dp[i][j]为假，dp[i][j] 只依赖 dp[i+1][j+1] 或 dp[i+k(k>=0)][j+2]的值。

---

简洁代码：

class Solution {public:    bool match(char* str, char* pattern)    {        int La = strlen(str);        int Lb = strlen(pattern);        if(La == 0 && Lb == 0) return true;        if(Lb == 0) return false;        bool dp[La+1][Lb+1];        memset(dp,0,sizeof(dp));        dp[La][Lb] = true;        for(int j = Lb -2 ; j>=0; j-=2){            if(pattern[j+1] == '*' && pattern[j] != '*'){                dp[La][j] = true;            }else{                break;            }        }        if(str[La-1] == pattern[Lb-1] || pattern[Lb-1]=='.')            dp[La-1][Lb-1] = true;        for(int i=La-1;i>=0;i--){            for(int j=Lb-2;j>=0;j--){                if(pattern[j+1] == '*'){                    int k = i;                    while(k

---

带注释代码

class Solution {public:    bool match(char* str, char* pattern)    {        int La = strlen(str);        int Lb = strlen(pattern);        if(La == 0 && Lb == 0) return true;        if(Lb == 0) return false;                //动态规划，从后向前推        bool dp[La+1][Lb+1];        memset(dp,0,sizeof(dp));        // 第一，dp[La][Lb]一定为真,两个空串        dp[La][Lb] = true;        // 第二，处理dp[i][Lb]部分;        // 表示pattern已经结束，str没有结束，所以全部为0                // 第三，处理dp[La][j]部分        // 表示str已经结束，pattern没有结束，所以当pattern结尾都是X*才会为真        for(int j = Lb -2 ; j>=0; j-=2){            if(pattern[j+1] == '*' && pattern[j] != '*'){                dp[La][j] = true;            }else{                break;            }        }                // 第四，处理dp[i][Lb-1]部分，由于*的存在，所以此部分需要特殊处理        // 表示pattern只剩最后一个字符，str没有结束        // 只有dp[La][Lb]有可能为真，其他都为假。        if(str[La-1] == pattern[Lb-1] || pattern[Lb-1]=='.')            dp[La-1][Lb-1] = true;                // 第五，打表dp[i][j],其中当pattern[j]=='*',所有dp[i][j]为假        // dp[i][j] 只依赖 dp[i+1][j+1] 和 dp[i+k(k>=0)][j+2]的值。        for(int i=La-1;i>=0;i--){            for(int j=Lb-2;j>=0;j--){                if(pattern[j+1] == '*'){                    int k = i;                    // 只有当 str[k] 和 pattern[j] 通配时                    // dp[i][j] 才依赖 dp[k][j+2]                    while(k

转载地址：http://ybwji.baihongyu.com/