首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符
  • 热度指数：180880 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}在计算机中，通配符是一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。让我们来学习通配符的匹配规则：
\hspace{23pt}\bullet\,\texttt{`*'} 符号代表匹配 0 个或以上的数字或字母；
\hspace{23pt}\bullet\,\texttt{`?'} 符号代表匹配 1 个数字或字母；
\hspace{23pt}\bullet\,小写字母字符代表匹配自身和自身的大写字母形态；
\hspace{23pt}\bullet\,大写字母字符代表匹配自身和自身的小写字母形态；
\hspace{23pt}\bullet\,其他字符代表匹配自身。

\hspace{15pt}现在，对于给定的通配符字符串 s 和目标字符串 p，不考虑大小写，请判断 s 是否可以匹配得到 p。如果可以，输出 \rm true；否则，输出 \rm false。

\hspace{15pt}在本题中，给定的字符串由 ASCII 码在 33 到 126 范围内的可见字符构成。您可以参阅下表获得其详细信息（您可能关注的内容是，这其中不包含空格、换行）。
../图片/AllAscii.png

输入描述:
\hspace{15pt}第一行输入一个长度为 1 \leqq {\rm len}(s) \leqq 100、由可见字符构成的通配符字符串 s。
\hspace{15pt}第二行输入一个长度为 1 \leqq {\rm len}(p) \leqq 100 、由可见字符构成的目标字符串 p。


输出描述:
\hspace{15pt}如果可以匹配得到，输出 \textrm{true}；否则，输出 \textrm{false}。
示例1

输入

z
zz

输出

false
示例2

输入

Z*
zz

输出

true

说明

\hspace{15pt}在这个样例中，\texttt{`*'} 匹配 \texttt{`z'}。注意，由于不区分大小写，\texttt{`Z'} 可以匹配 \texttt{`z'}。
示例3

输入

?*
zz

输出

true

说明

\hspace{15pt}在这个样例中，\texttt{`?'} 匹配 \texttt{`z'}、\texttt{`*'} 匹配 \texttt{`z'}。
示例4

输入

**Z
0QZz

输出

true

说明

\hspace{15pt}在这个样例中，其中一种匹配方法是：
\hspace{23pt}\bullet\,第一个 \texttt{`*'} 匹配 \texttt{；
\hspace{23pt}\bullet\,第二个 \texttt{`*'} 匹配 \texttt{`Z'}；
\hspace{23pt}\bullet\,第三个 \texttt{`Z'} 匹配 \texttt{`z'}。
示例5

输入

??**
zz

输出

true

说明

\hspace{15pt}\texttt{`*'} 可以匹配 0 个字符。
示例6

输入

HH?*
HH##1

输出

false

说明

\hspace{15pt}可被 \texttt{`*'} 和 \texttt{`?'} 匹配的字符不包含 \texttt{`\#'}。
算法知识视频讲解
添加回答
C
牛客71635794号头像 牛客71635794号
//6ms递归

#include <ctype.h>
#include <stdio.h>

int ans(char *a, int lenA, int i, char *b, int lenB, int j) {
    if (!(i < lenA) && j < lenB) return 0;
    if (!(i < lenA) && !(j < lenB)) return 1;
    if (a[i] == '?') {
        return isalnum(b[j]) && ans(a, lenA, i+1, b, lenB, j+1);
    } else if (a[i] == '*') {
        while(a[i+1] == '*') {
            i++;
        }
        if (a[i+1] == '\0') {
            return 1;
        }
        for (int k = j; k < lenB; ++k) {
            if (ans(a, lenA, i+1, b, lenB, k)) {
                return 1;
            }
        }
        return 0;
    } else {
        return tolower(a[i]) == tolower(b[j]) && ans(a, lenA, i+1, b, lenB, j+1);
    }
}

int main() {
    char a[101];
    char b[101];
    scanf("%s", a);
    scanf("%s", b);
    if (ans(a, strlen(a), 0, b, strlen(b), 0)) {
        printf("true");
    } else {
        printf("false");
    }
    return 0;
}
发表于 2024-09-22 21:37:11 回复(0)
C
彭洋a头像 彭洋a
//确实是很多时候就是递归想不明白，还是需要借鉴一下递归

#include <stdio.h>
#include <string.h>
#include <ctype.h>

int cmp_str(char *std, char *str)
{
  int i = 0, j = 0;

  while (i < strlen(std) && j < strlen(str))
  {
    if (std[i] == '?')
    {
      if (isdigit(str[j])||isalpha(str[j]))
        j++, i++;
      else
        return 0;
    }
    else if (std[i] == str[j])
      i++, j++;
    else if (std[i] == '*')
    {
      while (std[i + 1] == '*')
        i++;
      //三种情况 匹配0个字符 匹配下一个字符，匹配多个（std不动，还是*在匹配，str下移）
      return cmp_str(std + i + 1, str + j) || cmp_str(std + i + 1, str + j + 1) || cmp_str(std + i, str + j + 1);
    }
    else
      return 0;
  }

  if (i == strlen(std) && j == strlen(str))
    return 1;
  else
    return 0;
}

int main()
{
  char std[200];
  char str[200];
  while (scanf("%s %s",std,str) != EOF)
  {
    for (int k = 0; k < strlen(str); k++)
    {
        str[k] = tolower(str[k]);
    }
    for (int k = 0; k < strlen(std); k++)
    {
        std[k] = tolower(std[k]);
    }
    //全部替换成小写

    if (cmp_str(std, str) == 1)
    {
      printf("true\n");
    }
    else
      printf("false\n");
  }

  return 0;
}
发表于 2023-10-23 16:50:57 回复(0)
C
我不叫李大侠头像 我不叫李大侠 
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>

bool isCor(char c)
{
    if (isdigit(c) || islower(c)) {
        return true;
    }

    return false;
}

bool match(char *s1, char *s2)
{
    int i = 0; 
    int j = 0;
    int i_pre = 0;
    int j_pre = 0;
    int flag = 0;

    while (s2[j] != '\0') {
        s1[i] = tolower(s1[i]);
        s2[j] = tolower(s2[j]);
        if (s1[i] == '*' && isCor(s2[i])) {
            i_pre = i;
            j_pre = j;
            flag = 1;
            i++;
        } else if (s1[i] == '*') {
            i++;
        } else if (flag) {
            i = i_pre;
            j = j_pre + 1;
            flag = 0;
        } else {
            return false;
        }
    }

    while (s1[i] != '\0') {
        if (s1[i] != '*') {
            return false;
        }
        i++;
    }

    return true;
}
int main() {
    char str1[100] = {0};
    char str2[100] = {0};

    gets(str1);
    gets(str2);

    char *ret = match(str1, str2) ? "true" : "false";
    printf("%s\n", ret);
    return 0;
}

发表于 2023-08-31 10:59:29 回复(1)
C
学术垃圾头像 学术垃圾
为什么这个用例匹配结果是false啊，求大神指点
te?t*123
text1234
发表于 2023-04-16 18:51:37 回复(2)
C
已注销头像 已注销 
#include <stdio.h>
#include <string.h>
#define    N    100
int main()
{
    char s[N],p[N];
    int dp[N][N]={1},i,lenp,lens,j,k,flag;
    scanf("%s%s",p,s);
    lenp=strlen(p);
    lens=strlen(s);
    for(i=0;i<lenp;i++)
        if(p[i]>='A'&&p[i]<='Z')
            p[i]+='a'-'A';
    for(i=0;i<lens;i++)
        if(s[i]>='A'&&s[i]<='Z')
            s[i]+='a'-'A';
    for(i=0;i<lenp;i++)
    {
        for(j=0;j<lens;j++)
        {
            if(dp[i][j])
            {
                if(p[i]==s[j])
                {
                    dp[i+1][j+1]=1;
                }
                else if(p[i]=='*')
                {
                    dp[i+1][j]=1;
                    k=j;
                    while((s[k]>='0'&&s[k]<='9')||(s[k]>='a'&&s[k]<='z'))
                    {
                        dp[i+1][k+1]=1;
                        k++;
                    }
                }
                else if(p[i]=='?'&&((s[j]>='0'&&s[j]<='9')||(s[j]>='a'&&s[j]<='z')))
                {
                    dp[i+1][j+1]=1;
                }
            }
        }
    }
    if(dp[lenp][lens])
        printf("true");
    else
        printf("false");
    return 0;
}
疯狂打补丁。。。
发表于 2022-05-04 08:58:05 回复(0)
C
牛客743102380号头像 牛客743102380号 
#include<stdio.h>
#include<string.h>

int max(int a, int b)
{
    return a>b?a:b;
}
int match(char a[] ,char b[])
{
    int lena = strlen(a);
    int lenb = strlen(b);
    int dp[100][100] = {0};
    dp[0][0] = 1;
    for(int j = 0;j < lenb;j++)
    {
        if((b[j] == '.') || ((b[j] >= '0') && (b[j] <= '9')) || ((b[j] >= 'a') && (b[j] <= 'z')) || ((b[j] >= 'A') && (b[j] <= 'Z')))
        {
            continue;
        }
        else
        {
            return 0;
        }
    }
    for(int i = 1;i <= lena;i++)
    {
        if(a[i - 1] == '*')
        {
            dp[i][0] = 1;
        }
        else
        {
            break;
        }
    }
    for(int i = 1;i <= lena;i++)
    {
        for(int j = 1;j <= lenb;j++)
        {
            if(a[i - 1] == '?')
            {
                dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
            }
            if((a[i - 1] == b[j - 1]) || (a[i - 1] == b[j - 1] + 32) || (a[i - 1] == b[j - 1] - 32))
            {
                dp[i][j] = max(dp[i][j] , dp[i-1][j-1]);
            }
            if(a[i - 1] == '*')
            {
                dp[i][j] = max(dp[i][j] , (dp[i-1][j] || dp[i][j - 1]));
            }
        }
    }
    return dp[lena][lenb];
    
}

int main()
{
    int m;
    char a[100],b[100];
    while(scanf("%s",&a) != EOF)
    {
        scanf("%s",&b) ;
        m = match(a, b);
         if(m == 1)
    {
        printf("true\n");
    }
    else{
        printf("false\n");
    }
    }
}

发表于 2021-08-24 01:29:51 回复(0)
C
80后大叔头像 80后大叔

没全对，差一点点

#include<stdio.h>
int isChar(char C) {
    if((C >= 'A' && C <= 'Z') || (C >= '0' && C <= '9') || C == '.') {
        return 1;
    } else {
        return 0;
    }
}

char changeUp(char C) {
    if(C >= 'a' && C <= 'z') {
        C -= 32;
    }
    return C;
}
int getDP(char a[500], char b[500]) {
    int m = strlen(a);
    int n = strlen(b);
    int dp[500][500] = {0}, maxlen = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            char p = changeUp(a[i]);
            char q = changeUp(b[j]);
            if((p == q) || 
               ((p == '?' || p == '*') && isChar(q) == 1 )) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > maxlen) {
                    maxlen = dp[i][j];
//                     break;
//                     i--;
                }
            }
        }
    }
    return maxlen;
}
int main() {
    char a[500], b[500];
    while(gets(a) && gets(b)) {
        if(strstr(a, "*") == NULL && strstr(a, "?") == NULL) {
            if(strlen(a) == strlen(b)) {
                int result = 1;
                for(int i = 0; i < strlen(a); i++) {
                    if(a[i] != b[i]){
                        result = 0;;
                    }
                }
                if(result == 1) {
                    printf("true\n");
                } else {
                    printf("false\n");
                }
            } else {
                printf("false\n");
            }
            continue;
        }
        char sub[500] = {0};
        char *p = &a;
        char *q = p;
        while(*p != '\0') {
            if(*p != '*' && *p != '?') {
                q = p;
                break;
            }
            p++;
        }
        if(*p == '\0') {
            printf("true\n"); // 通配符字符串只包含*?，直接表示true
            continue;
        }
        int maxlen = 0;
        maxlen = getDP(a, b);
        int smallLen = strlen(a) < strlen(b) ? strlen(a): strlen(b);
//        printf("%d ", maxlen);
//        printf("%d\n", smallLen);
        if(maxlen >= smallLen) {
            printf("true\n");
        } else {
            printf("false\n");
        }

    }
}
发表于 2021-08-21 21:46:02 回复(0)
提交观点

问题信息

字符串
难度：
7条回答 36183浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串通配符

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号