LeetCode 刷题【44. 通配符匹配】

44. 通配符匹配

自己做（歇菜）

看题解

解：动态规划

官方代码

情况1：匹配一个任意字符，这时候只需要关注前面的匹配情况，前面如果匹配上了，延伸一个能匹配的字符还是能匹配，反之不匹配，即dp[i][j−1]

情况2：匹配任意长度的字符（0~xxx），这时候看上一轮的匹配的情况，上一轮即dp[i−1][j]，上一轮的*无论是什么，我们延伸后依然保持一致，如果上一轮匹配，那么这一轮依旧匹配，否则不匹配

• 首先处理p匹配串开头的*，可能是一个也可能有多个，这里默认*代表空字符，即表示，s主串的前0个元素和p匹配串的前i个元素匹配
• 匹配的过程中，如果为*，则算两种情况：
• 如果元素相等或者匹配字符为？，那么匹配的结果就看之前匹配能否匹配上，前面匹配上了，那么扩展一位能匹配的字符，依然能匹配，反之不匹配

class Solution {
public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));dp[0][0] = true;for (int i = 1; i <= n; ++i) {if (p[i - 1] == '*') {dp[0][i] = true;}else {break;}}for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p[j - 1] == '*') {dp[i][j] = dp[i][j - 1] | dp[i - 1][j];}else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {dp[i][j] = dp[i - 1][j - 1];}}}return dp[m][n];}
};