leetcode做题笔记44

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

目录

思路一：动态规划

分析：

总结：

思路一：动态规划

bool isMatch(char * s, char * p){int lens = strlen(s),lenp = strlen(p);int**dp = (int**)malloc(sizeof(int*)*(lens+1));for (int i = 0; i <= lens; ++i){*(dp+i) = (int*)malloc(sizeof(int)*(lenp+1));memset(*(dp+i), 0, sizeof(int)*(lenp+1));}dp[0][0] = 1;for(int i = 1;i<=lenp;i++){if(p[i-1]=='*')dp[0][i] = 1;else break;}for (int i = 1; i <= lens; i++){for (int j = 1; j <= lenp; j++){if (s[i-1] == p[j-1])dp[i][j] = dp[i-1][j-1];else{if (p[j-1] == '?')dp[i][j] = dp[i-1][j-1];else if (p[j-1] == '*')dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];}}}return dp[lens][lenp];
}

时间复杂度O(n^3)，空间复杂度O(n^2)

分析：

本题要实现*和？的匹配机制，可将每次匹配的字符放入一个二位数组判断是否用过，通过每列判断是否符合设置二维数组该位置的值。最后输出该位置的值

总结：

本题可使用动态规划和回溯解法进行解答，主要考察了对动态规划及回溯的应用，利用字符判断设置二维数组值后输出。