题解 | #字符串通配符#

字符串通配符

题目描述

在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。

要求：

实现如下2个通配符：

$\ast *$：匹配0个或以上的字符

（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）

？：匹配1个字符

方法一：动态规划方法

解题思路

对于本题目的求解，利用动态规划，dp[i][j]表示pattern前i个字符和字符串str前j个字符的匹配情况。如果匹配，dp[i][j] = 1，如果不匹配，dp[i][j] = 0。dp[0][0] = 0，首先遍历一遍动态数组，假设pattern第i个字符为c1，str数组第j个字符为c2，有以下情况：

1、如果c1为*，可以匹配或者不匹配。如果匹配的话，dp[i][j] = dp[i][j-1],如果不匹配，dp[i][j] = dp[i-1][j]。 2、如果c1不为*，考虑c2，如果c2为数字，那么c1必须为？或者和c2相同才能匹配成功。如果c2为字母，那么c1必须为？或者和c2相同才能匹配成功，如果c2既不是数字也不是字母，那么c1必须和c2相同才能匹配成功。

解题代码

#include<bits/stdc++.h>
using namespace std;

int match_string(string str,string pattern)
{
    int len1 = str.size();
    int len2 = pattern.size();
    vector<vector<int> > dp(len2+1,vector<int>(len1+1,0));
    //多加一行一列作为初始初值所用
    dp[0][0] = 1;//初始化
    for(int i=1;i <=len2;i++){
        char ch1 = pattern[i-1];
        ////设置每次循环的初值，即当星号不出现在首位时，匹配字符串的初值都为false
        dp[i][0] = dp[i-1][0]&&(ch1=='*');
        for(int j=1;j<=len1;j++){
            char ch2 = str[j-1];
        	if(ch1=='*')
            {
                dp[i][j]=dp[i-1][j]||dp[i][j-1]; //当匹配字符为*号时，可以匹配0个或者多个
            }else
            {
                if(isalpha(ch2))
                {//ch2为字母时，尝试是否能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1=='?'||(ch2==ch1||ch2==(ch1+('A'-'a'))||ch2==(ch1-('A'-'a'))));
                }
                else if(isdigit(ch2))
                {//ch2为数字时，尝试是否能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1=='?'||(ch1==ch2));
                }
                else
                {//ch2既不为字母也不为数字时，只有ch1和ch2相同才能匹配
                    dp[i][j]=dp[i-1][j-1]&&(ch1==ch2);
                }
            }
    	}
    }
    return dp[len2][len1];
}
int main(){
    string str1,str2;
    while(cin >> str1 >> str2)
    {
       int flag =  match_string(str2,str1);
       if(flag)
       {
           cout << "true" << endl;
       }
        else
        {
           cout << "false" << endl;
       }
    }
    
}

复杂度分析

时间复杂度：遍历dp数组，因此时间复杂度为$O(NM)O(NM)$，其中N为str的长度，M为pattern的长度。

空间复杂度：使用dp数组，因此空间复杂度为$O(NM)O(NM)$。

方法二：递归的方法

解题思路

采用递归的方法，有如下情况：

1、如果为？，只能匹配数字或字符，匹配一个字符，从下一个位置开始继续递归。

2、如果为*，因为多个$\ast *$和一个$\ast *$的效果是一样的，考虑*匹配的情况，匹配0个，1个或者多个，然后分为三种情况进行递归。

3、如果为其他字符，则必须要求匹配的字符相同才能进行接下来的递归。

最后，如果两个字符串同时结束，则说明匹配成功。如果两个字符串中不同时结束，那么说明匹配失败。

解题代码

#include<bits/stdc++.h>
using namespace std;

bool match(const char* s,const char* p)
{
    //两个字符串同时结束,返回true
    if((*p=='\0')&&(*s=='\0'))
    {
        return true;
    }
    if((*p=='\0')||(*s=='\0'))
    {
        return false;
    }
    if(*p=='?')
    {//通配符为？时
        if(!isdigit(*s)&&!isalpha(*s))
        {//只能匹配数字或字母
            return false;
        }
        //匹配一个字符，从下一个位置开始继续匹配
        return match(s+1,p+1);
    }
    else if(*p=='*')
    {//通配符为！时
        while(*p=='*')
        {//多个*和一个*效果相同
            p++;
        }
        p--;
        //遇到*号，匹配0个（str+1,str1不用动），匹配1个（str和str1都往前移动1位），匹配多个（str不用动，str+1）
        return match(s,p+1) || match(s+1,p+1) ||  match(s+1,p);
    }else if(tolower(*p)==tolower(*s)){//不区分大小写
         //当前两字符相等，则进行下一个字符的匹配
        return match(s+1,p+1);
    }
    return false;//不满足上述三种情况，不匹配
}

int main(){
    string p,s;
    while(cin>>p>>s){
        bool res = match(s.c_str(),p.c_str());
        if(res){
            cout<<"true"<<endl;
        }else{
            cout<<"false"<<endl;
        }
    }
    return 0;
}

复杂度分析

时间复杂度：最坏情况下递归呈二叉树样式递归，因此时间复杂度为$O(2^n)O(2^n)$。

空间复杂度：使用递归，递归栈申请内存空间，因此空间复杂度为$O(N)O(N)$,其中N为递归栈的大小。