通配符匹配

2019-11-06 08:00:02

字体：大中小

来源：转载

供稿：网友

通配符匹配

问题来源： 44. Wildcard Matching

#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;bool dp[10001][10001]; //dp[i][j]表示string的子串（0～i位置的子串），与pattern的子串（0～j位置的子串）是否匹配bool isMatch(char* s, char* p) { int len_s = strlen(s); int len_p = strlen(p); //把多余的＊变成一个＊ //比如：a**b***c变成a*b*c bool flag = true; int writeIndex = 0; for(int i=0; i<len_p; i++){ if (p[i]=='*') { if (flag==true) { p[writeIndex++] = '*'; flag = false; } } else{ p[writeIndex++] = p[i]; flag = true; } } for (int i=0; i<=len_s; i++) { for (int j=0; j<=writeIndex; j++) { dp[i][j] = false; } } if(writeIndex>0&&p[0]=='*'){ //当p为一个*,s为空时，为true dp[0][1] = true; } dp[0][0] = true; //p和s都为空时，为true for (int i=1; i<=len_s; i++) { for (int j=1; j<=writeIndex; j++) { if (s[i-1]==p[j-1]||p[j-1]=='?') { //理解，见笔记 dp[i][j] = dp[i-1][j-1]; } else if(p[j-1]=='*'){ dp[i][j] = dp[i][j-1]||dp[i-1][j]; } } } return dp[len_s][writeIndex];}int main(int argc, const char * argv[]) { char s[] = "aa"; char p[] = "a*"; bool ans = isMatch(s, p); PRintf(ans==true?"true/n":"false/n"); return 0;}

注意：把多余的＊变成一个＊的方法：

bool flag = true; int writeIndex = 0; for(int i=0; i<len_p; i++){ if (p[i]=='*') { if (flag==true) { p[writeIndex++] = '*'; flag = false; } } else{ p[writeIndex++] = p[i]; flag = true; } }

在此输入正文

上一篇：HDU1172 猜数字

下一篇：Dubbo学习笔记（五）------DubboProtocol理解之Refer