Leetcode 044 Wildcard Matching（DP）

本文主要是介绍Leetcode 044 Wildcard Matching（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：Leetcode 044 Wildcard Matching

解题思路：动态规划，dp[i][j]表示s[0]~s[i-1]和p[0]~p[j-1]是否可以匹配。转移方程有：

    s[i] == p[j] 时：dp[i][j] |= dp[i-1][j-1]

    p[j] == '*'时：dp[i][j] |= dp[i-1][j] | dp[i][j-1]   （分别对应*匹配0个和多个的情况）

class Solution {public:bool isMatch(string s, string p) {int ns = s.size(), np = p.size();bool** dp = new bool*[ns + 1];for (int i = 0; i <= ns; i++) {dp[i] = new bool[np + 1];for (int j = 0; j <= np; j++) dp[i][j] = false;}dp[0][0] = true;for (int i = 0; i <= ns; i++) {for (int j = 1; j <= np; j++) {if (i && (s[i-1] == p[j-1] || p[j-1] == '?' || p[j-1] == '*'))dp[i][j] |= dp[i-1][j-1];if (p[j-1] == '*') {if (i) dp[i][j] |= dp[i-1][j];dp[i][j] |= dp[i][j-1];}}}return dp[ns][np];}
};

这篇关于Leetcode 044 Wildcard Matching（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---