字符串通配符*？匹配——C语言递归方法

【问题描述】判断两个字符串是否匹配，其中一个字符串中包括通配符*或？（串）。

*代表0个或多个字符，？代表一个字符
【输入形式】分两行入两个字符串，以#结束，其中一个字符串中包括通配符*或？（串），另一个为不包含*和？的确定字符串
【输出形式】判断两个字符串是否匹配，若匹配，输出yes，不匹配输出no
【样例输入】

 da?a*tu*e#
 datastructure#
【样例输出】
 yes
【样例说明】 第一个字符串中包含通配符，第二个字符串为确定字符串。

字符串中可能有空格，字母均为小写字母。

初看题目，以为这个题目很简单，用上两个变量i，j对两个字符串遍历，挨个匹配，遇'?'则i++,j++,遇'*',则i++，j一直往后找到与i相等的字符就行了。

结果一看测试数据，才发现还是我想得太简单了：

*e*e*every

new and innovative websites are being created every

如上，和我预先设想的不同，按次序匹配的话，"every"将会与"ebsit"匹配，则最终会返回"no"

所以，得想个办法，当发现*后的匹配不成功时，则回到*号后，跳过比上一轮多的字符，尝试匹配。

如下：

*e*e*every

new and innovative websites are being created every

*e*e*every

new and innovative websites are being created every  //空格也是作为字符匹配的

*e*e*every

new and innovative websites are being created every

*e*e*every

new and innovative websites are being created every

*e*e*every

new and innovative websites are being created every

*e*e*every

new and innovative websites are being created every

自然而然地，我想到了——递归——正好如果匹配不成功，就可以返回到上一次调用函数时，上代码！

int panduan(int i,int j)  //panduan就是判断啦~为什么是int返回值不用bool，因为c没有bool->_<-
{                         //i与j分别表示第一个与第二个字符串的某个下标，作用类似于指针
    while(a[i]==b[j])     //相等的话就将i与j都后移
    {
        if(a[i]=='#') return 1; //这个判断要放前面，否则可能有越界风险
        i++;j++;
    }                     //从while里面出来了，那就是对应字符不相等了，就进入下面的判断了
    if(a[i]!='?'&&a[i]!='*') return 0;  //匹配失败
    else if(a[i]=='?') return panduan(i+1,j+1);
    else if(a[i]=='*')
    {
        while(a[i+1]=='?'){i++;j++;}  //当*与多个?在一块的时候，需要这个判断
        while(a[i+1]=='*') i++;      //一个*跳多个或不跳字符，多个*也是跳多个或不跳字符
        if(panduan(i+1,j)) return 1;
        else{
            while(j

这段代码比较繁琐，肯定会有更加优化的写法；该题解法思路上也有更加优化的解法(比如DP)。

作者上传该题解意在提供不同的思想，欢迎批评指正。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/564036.html