请实现支持'?'and'*'.的通配符模式匹配
正则表达式问题，典型的动态规划问题
关键点 s串遇到一个p串*时的思路：
若两者的前面部分可通配 那么当前*仅仅通配一个对应字符即可若s串与*前面部分通配 那么当前*通配空串即可若s串前面部分与当前串通配 那么当前*再多通配一个对应字符即可
易错点，单独s串为空串 p串包含*情况 即 dp[0][i]需要提前计算好
下标问题：dp[1][1]表示s[0]与p[0]匹配情况
bool dp[1000][1000];//dp[i][j]表示s的前面i部分 与 p的前面j部分是否匹配 bool isMatch(const char *s, const char *p) { int length_s=strlen(s); int length_p=strlen(p);//长度 dp[0][0]=true; //首先考察 s串为空 而p串包含*的情况 该类情况能够完成匹配 for(int i=1;i<=length_p;i++) { if(p[i-1]=='*') dp[0][i]=dp[0][i-1]; //只要遇到一个* else dp[0][i]=false;//一旦遇到普通的？ 或者字符 那么一定不能通配 } for(int i=1;i<=length_s;i++) for(int j=1;j<=length_p;j++) { if(s[i-1]==p[j-1] || p[j-1]=='?') //对应相等 或者采取? 完成通配 { dp[i][j]=dp[i-1][j-1];//取决于之前的串能否匹配 continue; } if(p[j-1]=='*') { //遇到*可以有三种情况 //若两者的前面部分可通配 那么当前*仅仅通配一个对应字符即可 //若s串与*前面部分通配 那么当前*通配空串即可 //若s串前面部分与当前串通配 那么当前*再多通配一个对应字符即可 dp[i][j]=dp[i-1][j-1]||dp[i][j-1]||dp[i-1][j]; continue; } dp[i][j]=false;//末尾都是普通的字符 一定无法通配 } return dp[length_s][length_p]; }
也可采用模拟推演其中过程
bool isMatch(const char *s, const char *p) { int length_s=strlen(s); int length_p=strlen(p);//两个串长度 int p_recall=0; //p中*的位置 int s_recall=0; //s中对应p中*的位置 bool has_star=false;//是否有可用的 * int p_s=0; int p_p=0;//两个串匹配过程 下标 while(p_s<length_s) //以被匹配串s 作为移动串 看过程中能否完成匹配 { if(s[p_s]==p[p_p] || p[p_p]=='?') //若对应字符相等 或者匹配串对应位置为 ？ { p_s++; p_p++;//匹配成功 s p串考察位置后移 } else if(p[p_p]=='*') //对应位置为* { p_recall=++p_p; //考察p串下一个元素 s_recall=p_s;// s串回溯点 //先忽视* 考察p串下一个元素 与 s的当前元素 即p_s不作移动 has_star=true; } else //其它情况 即对应字符不相等 也不含有通配符 { if(has_star) //利用之前* { p_s=++s_recall; //下一个s串考察位置 为 之前的s_recall往后一个 p_p=p_recall;//下一个p串考察位置为 * 后面一个 } else { return false; } } } while(p[p_p]=='*') //p串可能剩余* 全部对应为空串即可 p_p++; return p_s==length_s && p_p==length_p; }
