下面是我自己的解答
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define MAX_LEN 128
bool match(char *S,char *P)
{
bool F[MAX_LEN][MAX_LEN];
int lenS = strlen(S);
int lenP = strlen(P);
for (int i = 0; i<MAX_LEN; i++)
{
for (int j = 0; j<MAX_LEN; j++)
{
F[i][j] = false;
}
}
F[0][0] = true;
for (int i = 1; i <=lenP; i++)
{
for (int j = 1; j<=lenS; j++)
{
if (F[i-1][j-1])
{
if (S[j-1] == P[i-1] || P[i-1] == '?' || P[i-1] == '*')
{
F[i][j] = true;
continue;
}
}
if (F[i-1][j])
{
if (P[i-1] == '*')
{
F[i][j] = true;
continue;
}
}
if (F[i][j-1])
{
if (P[i-1] == '*')
{
F[i][j] = true;
continue;
}
}
}
}
return F[lenP][lenS];
}
int _tmain(int argc,_TCHAR* argv[])
{
char *S = "CISCO";
char *P = "*C?";
bool isMatch = match(S,P);
if (isMatch)
{
printf("Match\n");
}
else
{
printf("No Match\n");
}
return 0;
}
网上有一个更详细的解答：
网上有一个更详细的描述
参考：http://blog.csdn.net/lifajun90/article/details/10582733
解法一：
由于以前做过一个类似的题目http://soj.me/1197,所以我的第一印象就是用动态规划，具体思路如下：
用dp[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否匹配，那么状态转移情况如下：
if (dp[i-1][j-1] && (s[i] == p[j] || '?' == p[j])) dp[i][j] = true,即如果前i-1和前j-1个字符匹配，当前字符也匹配，那么前i个和前j个也匹配。
如果p的当前字符为'*'号，那么可以分两种情况：
(1) 如果dp[i-1][j-1]，那么p的前j个字符和s的前k(i-1<=k<=len_s)个字符都匹配，注意这里有一个i-1，因为*可以匹配空串。
(2)如果dp[i][j-1]，即s的前i个字符和字符串p的前j-1个字符，那么p的前j个字符和s的前k(i<=k<=len_s)个字符匹配，注意这里没有i-1，因为这是让*去匹配i后面的字符串。
这种解法的时间复杂度和空间复杂度都为O(N^2)，所以在leetcode上只能过小数据不能过大数据。
具体实现代码如下：
- //dp解法
- constintN=105;
- booldp[N][N];
- classSolution{
- public:
- boolisMatch(char*s,char*p){
- //StarttypingyourC/C++solutionbelow
- //DONOTwriteintmain()function
- if(*s=='\0'){
- while(*p=='*')p++;
- return*p=='\0';
- }
- if(*p=='\0')returnfalse;
- memset(dp,false,153); background-color:inherit; font-weight:bold">sizeofdp);
- dp[0][0]=true;
- intlen_s=strlen(s),len_p=strlen(p);
- for(intj=1;j<=len_p;j++){
- inti=1;i<=len_s;i++){
- if(dp[i-1][j-1]&&(s[i-1]==p[j-1]||'?'==p[j-1]))dp[i][j]=if('*'==p[j-1]){
- if(dp[i-1][j-1]){
- intk=i-1;k<=len_s;k++)dp[k][j]=true;
- break;
- }elseif(dp[i][j-1]){
- intk=i;k<=len_s;k++)dp[k][j]=break;
- }
- returndp[len_s][len_p];
- };
解法二(递归解法)：
解法一不能过大数据的原因在于两层for循环其实执行了多余的匹配过程，其实对于这种匹配来说如果*s和*p相等的话我们可以直接把指针往后移动，从而把数据规模缩小。这种做法的难点同样在对*号的处理上，因为*号可以匹配多个字符，所以在递归解法中需要回溯。
因为递归和回溯的代价都太高，所以该解法也只能过小数据，不能过大数据。
具体代码实现如下：
copy