字符串通配符(递归+动态规划)

题目简述:实现如下2个通配符:
*:匹配0个或以上的字符(字符由英文字母和数字0-9组成,不区分大小写。下同)
?:匹配1个字符
详细地址:https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036?tpId=37&tags=&title=&diffculty=0&judgeStatus=0&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
参考:https://www.nowcoder.com/profile/8370150/codeBookDetail?submissionId=12740159

#include<iostream>
using namespace std;

bool match(char *str1, char *str2)
    {
    if(*str1 == '\0'  && *str2 == '\0')
        return true;
    else if(*str1 == '\0' || *str2 == '\0')
        return false;
    if(*str1 == '?')
        return match(str1+1, str2+1);
    else if(*str1 == '*')
        return match(str1+1, str2) || match(str1+1, str2+1) || match(str1, str2+1);
    else if(*str1 == *str2)
        return match(str1+1, str2+1);
    return false;
}

int main()
    {
    char str1[100], str2[100];
    while(cin>>str1>>str2)
        {
        if(match(str1, str2))
            cout<<"true"<<endl;
        else
            cout<<"false"<<endl;
    }

    return 0;
}

参考:https://www.nowcoder.com/profile/1076385/codeBookDetail?submissionId=12801707

#include<iostream>
#include<string>
#include<vector>

using namespace std;

#define max(a,b) (a>b)?a:b;

int main()
    {
    string str1,str2;
    while(cin>>str1>>str2)
        {      
        int len1=str1.size();
        int len2=str2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        dp[0][0]=1;
        for(int i=1;i<len1+1;i++)
            {
            char ch=str1[i-1];
            dp[i][0]=dp[i-1][0]&&(ch=='*');
            for(int j=1;j<len2+1;j++)
                {
                if(str1[i-1]=='*')
                    {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
                else
                    {
                    dp[i][j]=dp[i-1][j-1]&&(str1[i-1]=='?'||str1[i-1]==str2[j-1]);
                }
            }
        }
        if(dp[len1][len2]==1)
            {
            cout<<"true"<<endl;
        }
        else
            {
            cout<<"false"<<endl;
        }
    }
    return 0;
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务