题目
? ? 正则表达式匹配? '*'通配符的用法为 (字母)*可以匹配n个该字母或0个该字母,'.'可以作为任意的字母。例子 ：主串："zaaab", 匹配串: ".a*b" 返回"匹配成功",反之返回"匹配失败"；
思路分析
? ? 首先应该要做的是对两字符串进行同时遍历, 为了清晰思路我们就采用递归，我们要思考的是最小子问题的条件。（我们似乎能隐隐约约看到动态规划的影子）
?代码展示
#include<stdio.h>
#include<string.h>
#define M 255
int Marry(char *, int, char *, int);
int main()
{//str1为主串, str2为匹配串;
printf("请输入匹配串和主串\n");
char str1[M], str2[M];
gets(str2);
gets(str1);
if(Marry(str1, 0, str2, 0)){
printf("匹配!\n");
}else{
printf("不匹配!\n");
}
return 0;
}
int Marry(char *str1, int i, char *str2, int j)
{
if(i < strlen(str1) && j < strlen(str2)){
if(str1[i]==str2[j] || str2[j] == '.'){//相等时;
if(str2[j + 1] == '*' && j < strlen(str2) - 1){
return Marry(str1, i + 1, str2, j) || Marry(str1, i, str2, j + 2);
}else{
return Marry(str1, i + 1, str2, j + 1);
}
}else{//不相等时;
if(str2[j + 1] == '*' && j < strlen(str2) - 1){
return Marry(str1, i , str2, j + 2);
}else{
return 0;
}
}
}else{
//匹配串走完了;
if(j == strlen(str2))
return (i == strlen(str1)) ? 1 : 0;
//主串走完了, 匹配串未走完;
//情况一 : 匹配串剩下的字符都为通配符;
//情况二 ；匹配串剩下的字符不都为通配符;
int temp = 1;
for(; j < strlen(str2); j += 2){
if(j < strlen(str2) - 1 && str2[j + 1] != '*'){
temp = 0;
}
}
return (temp && j == strlen(str2)) ? 1 : 0;
/*temp用于判断是否匹配,j==strlen(str2)用于判断剩下的字符串的奇偶性,奇数是最后一个字符不为通配符*/
}
}运行结果为：
代码分析
? ? 当遍历的指针有一个越界时，我们就要判断哪一个指针越界，如果匹配串走完了，我们只要判断主串指针的位置就可以判断出结果。如果是主串走完了，那就要对剩下位走完的匹配串进行判断，剩下的匹配串都为(字母)*的通配符并且剩下的匹配串长度为偶数，就说明当前的为主串匹配成功，反之说明匹配失败。