Leetcode10.正则表达式匹配-创新互联

创新互联-专业网站定制、快速模板网站建设、高性价比灵山网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式灵山网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖灵山地区。费用合理售后完善，10多年实体公司更值得信赖。动态规划

解题思路

class Solution {public:
    bool isMatch(string s, string p) {int m = s.size(), n = p.size();
        vector>dp(m+1, vector(n+1, false));

        dp[0][0] = true;
        for(int j = 1; j< n + 1; j++) {if(p[j - 1] == '*') {dp[0][j] = dp[0][j - 2];
            }
        }

        for(int i = 1; i< m + 1; i++) {for (int j = 1; j< n + 1; j++) {if(s[i - 1] == p[j - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];
                }
                else if(p[j - 1] == '*') {if (s[i - 1] != p[j - 2] && p[j - 2] != '.') {dp[i][j] = dp[i][j-2];
                    }
                    else {dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

时间复杂度：O(mn)；
空间复杂度：O(mn)。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：Leetcode10.正则表达式匹配-创新互联
URL链接：http://cxhlcq.com/article/psdsd.html