首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符

热度指数：180681 时间限制：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

输入描述:

第一行输入一个长度为 、由可见字符构成的通配符字符串 。
第二行输入一个长度为  、由可见字符构成的目标字符串 。

输出描述:

如果可以匹配得到，输出 ；否则，输出 。

示例1

输入

z
zz

输出

false

示例2

输入

Z*
zz

输出

true

说明

在这个样例中， 匹配 。注意，由于不区分大小写， 可以匹配 。

示例3

输入

?*
zz

输出

true

说明

在这个样例中， 匹配 、 匹配 。

示例4

输入

**Z
0QZz

输出

true

说明

在这个样例中，其中一种匹配方法是：
第一个  匹配 ；
第二个  匹配 ；
第三个  匹配 。

示例5

输入

??**
zz

输出

true

说明

 可以匹配  个字符。

示例6

输入

HH?*
HH##1

输出

false

说明

可被  和  匹配的字符不包含 。

算法知识视频讲解

Python

牛客590711274号

发现正则化很多上传的是错的，或者超时。这个是自己做的降低复杂度的版本可以参考下。

#正则化，发现会超时，对输入进行了进一步处理降低复杂度就行了
import re 
while True:
    try:
        str1 = input()#记录第一行
        str2 = input()#记录第二行
        str1 = list(str1)
        counter=0#初始判定值
        for i in range (len(str1)):
            if str1[i] == "*" and counter ==0:
                counter = 1#当为相隔后第一个*时，保留此*并继续
            elif str1[i] == "*" and counter ==1:#当后续依然为*时，去除多余*因为*本身代表0-n个，从而减小计算复杂度
                str1[i] = ""#比如最后一个例子“h*h*ah**ha*h**h***hha” 重复*太多复杂度太大
            else:
                counter=0#一旦不是连续的*则重置判定值
        str1=''.join(str1)#合并为str
        str1 = str1.lower()
        str2 = str2.lower()#不分大小写，统一小写处理
        str1=str1.replace('?', '[0-9 a-z]')#统一小写+数字，不能用\w因为\w包括下划线，别涂省事规规矩矩打上
        str1=str1.replace('*','[0-9 a-z]*')#统一小写+数字 *代表0或多个
        str1=str1.replace('.','\.' )#由于.本身代表匹配除换行符以外的任意字符，需要转义
        str1 = "^"+str1+"$"
        search = re.match(str1, str2)#这道题用match()，如果是要求匹配整个字符串，直到找到一个匹配的规则的字符串则用search()
        if search != None:
            print('true')
        else:
            print('false')
    except:
        break

编辑于 2021-07-01 19:47:02 回复(0)

Python

牛客980779794号

def match(i,j,b,a,ma):
    if i==0&nbs***bsp;j==0:
        return ma[i][j]
    if a[j-1]=='*':
        ma[i][j]=match(i-1,j-1,b,a,ma)&nbs***bsp;match(i-1,j,b,a,ma)&nbs***bsp;match(i,j-1,b,a,ma)
        return ma[i][j]
    if a[j-1]=='?' and (b[i-1].isalpha()&nbs***bsp;b[i-1].isdigit()):
        ma[i][j]=match(i-1,j-1,b,a,ma)
        return ma[i][j]
    return (match(i-1,j-1,b,a,ma) and a[j-1]==b[i-1])
while True:
    try:
        a = input().lower()
        b = input().lower()
    except:
        break
    ma=[[False]*(len(a)+1) for i in range(len(b)+1)]
    ma[0][0]=True
    if a[0]=='*':
        ma[0][1]=True
    if match(len(b),len(a),b,a,ma):
        print('true')
    else:

似乎题库发生了改变，用动态分析勉强解决了问题。

编辑于 2021-06-22 23:12:39 回复(0)

Python

天才小学生小邓

from fnmatch import fnmatch
while True:
    try:
        a = input()
        b = input()
        c = fnmatch(b,a)
        if c == False:
            print('false')
        else:
            print('true')
    except:
        break

我的解法有点无聊...fnmatch输出本身就是布尔值。

发表于 2021-05-07 16:25:22 回复(1)

Python

牛客诶谁

import re

while True:
    try:
        reg = input().strip()
        s = input().strip()
        
        reg = reg.replace('?', '\w{1}').replace('.', '\.').replace('*', '\w*')
        c = re.findall(reg, s)
        if s in c and len(c) == 1:
            print('true')
        else:
            print('false')
    except:
        break

发表于 2021-05-04 22:22:15 回复(0)

Python

二年三班的牛客

while True:
    try:
        str1 = input()
        str2 = input()
        flag = 0
        i = 0
        j = 0
        while i < len(str1):
            if str1[i] == str2[j]:
                i += 1
                j += 1
            elif str1[i] != '?' and str1[i] != '*':
                flag = 1
                break
            elif str1[i] == '?':
                i += 1
                j += 1
            elif str1[i] == '*':
                if i != len(str1) - 1:
                    if str1[i+1] not in str2[j:] and str1[i+1] != '?':
                        flag = 1
                        break
                    elif str1[i+1] in str2[j:]:
                        i += 1
                        j += 1
                i += 1
                j += 1
        if flag == 0:
            print('true')
        elif flag == 1:
            print('false')
    except EOFError:
        break

发表于 2021-03-29 01:38:36 回复(0)

Python

星凌九天

用*和？将第一个字符串分割，去除掉空字符串，剩下的部分如果都在第二个字符串即可

while True:
try:
list1=input().split('?')
list3=[]
str4=input()
y=1
for i in list1:
if '*'in i:
list2=i.split('*')
list3+=list2
else:
list3.append(i)
for i in list3:
if i=='':
list3.remove(i)
for i in list3:
if not i in str4:
y=0
if y:
print('true')
else:
print('false')
except:
break

发表于 2021-03-25 22:40:20 回复(0)

Python

喵阿三

发现通过的代码里面大家都用的错的

while True:
    try:
        a = input()
        b = input()
        i, j, k = 0, 0, 1
        while i < len(a) and j < len(b):
            if a[i] == b[j]&nbs***bsp;a[i] == '?':
                i += 1
                j += 1
            elif a[i] == '*':
                if i+1 == len(a):
                    break
                elif a[i+1] == b[j+1]&nbs***bsp;a[i+1] == '?':
                    i += 1
                    j += 1
                elif a[i+1] == b[j]:
                    i += 1
                else:
                    j += 1
            else:
                k = 0
                break
        if k == 0:
            print('false')
        else:
            print('true')
    except Exception() as e:
        print(e)
        break

发表于 2021-02-14 08:26:21 回复(0)

Python

大溪地渔民

import re


while True:
    try:
        p, t = input(), input()
        p = p.replace("?", "[A-Za-z0-9]").replace("*", "[A-Za-z0-9]*").replace(".", "\.")
        p = "^" + p +"$"
        if re.match(p, t):
            print("true")
        else:
            print("false")
    except:
        break

发表于 2020-12-18 12:55:32 回复(0)

Python

gu_xing

def match(reg, s):
    i = 0
    flag = False
    for j, v in enumerate(reg):
        if v == '*':
            flag = True
            continue

        elif v == s[i]&nbs***bsp;v == '?':
            i += 1
            continue

        elif flag == True:
            while s[i] != v:
                i += 1
                if i >= len(s):
                    return 'false'
            flag = False
            i += 1

        else:
            return 'false'
    else:
        return 'true'


while True:
    try:

        reg, s = input(), input()
        print(match(reg, s))
    except:
        break

发表于 2020-08-10 13:27:22 回复(0)

Python

ShadowAnt_TC

def error_index(string):
    # 输出非法字符的位置
    ans = []
    for i in range(len(string)):
        c = string[i]
        if c.isalpha() or c.isnumeric() or c=='*' or c=='?':
            continue
        else:
            ans.append(i)
    return ans

def split_by_index(string, index):
    # 通过非法符号的位置进行划分
    ans = []
    index.insert(0, -1)
    index.append(len(string))
    lengh = len(index)
    for i in range(lengh-1):
        temp = string[index[i]+1: index[i+1]]
        if temp!='':
            ans.append(temp)
    return ans

def error_cmp(str1,str2,index1,index2):
    # 比较非法字符是否一样
    for i,j in zip(index1, index2):
        if str1[i]!=str2[i]:
            return False
    return True

def eq(str1, str2):
    # 比较通配符 str2是纯字母数字
    len1, len2 = len(str1), len(str2)
    if len1!=len2 and '*' not in str1:
        return False
    matrix = [[False for j in range(len2)] for i in range(len1)]
    if str1[0]=='*' or str1[0]=='?': matrix[0][0] = True
    else: 
        if str1[0]==str2[0]: matrix[0][0] = True

    for i in range(1, len1):
        if str1[i]=='*' and matrix[i-1][0]:
            matrix[i][0] = True
        else:
            matrix[i][0] = False
    
    # 重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点
    for i in range(1, len1):
        for j in range(1, len2):
            if str1[i]=='*':
                matrix[i][j] = matrix[i-1][j] or matrix[i][j-1]
            else:
                matrix[i][j] = matrix[i-1][j-1] and (str1[i]=='?'&nbs***bsp;str1[i]==str2[j])
    return matrix[len1-1][len2-1]
            

while True:
    try:
        error = 0
        expression, todo = input(), input()
        exp_index, todo_index = error_index(expression), error_index(todo)
        if len(exp_index)!= len(todo_index) or not error_cmp(expression, todo, exp_index, todo_index):
            error = 1
            break
        exp_split, todo_split = split_by_index(expression, exp_index), split_by_index(todo, todo_index)
        for str1,str2 in zip(exp_split, todo_split):
            if not eq(str1, str2):
                error = 1
                break
        if error: 
            print('false')
        else: 
            print('true')
    except:
        break

思想是先找字符以外的字符，再对这些非法字符进行split，比较这些非法字符是否一样，不一样直接退出。

再对分割后的子串进行通配符比较。

https://blog.csdn.net/weixin_38823568/article/details/81482046

https://blog.csdn.net/gldemo/article/details/47678159

编辑于 2020-07-30 22:02:50 回复(0)

Python

君临天下201804050931706

while True:
    try:
        str1 = input()
        str2 = input()
        x = 0
        y = 0
        flag=True
        while x<len(str1)-1 and y<len(str2)-1:
            if(str1[x]==str2[y] or str1[x]=="?"):
                x+=1
                y+=1
            elif(str1[x]=="*"):
                if(str1[x+1]==str2[y+1]):
                    x+=1
                    y+=1
                else:
                    y+=1
            else:
                flag=False
                break
        if(flag):
            print("true")
        else:
            print("false")
    except:
        break

发表于 2020-07-13 09:24:38 回复(1)

Python

Nwsuixew

import re

while True:
    try:
        rule = list(input())
        to_be_search = input()
        
        for i in range(len(rule)):
            if rule[i] == '.':
                rule[i] = '\.'
            elif rule[i] == '?':
                rule[i] = '.'
            elif rule[i] == '*':
                rule[i] = '.*'
        
        res = re.search(''.join(rule), to_be_search)
        if res:
            print('true')
        else:
            print('false')
        
    except:
        break

发表于 2020-03-24 11:26:25 回复(0)

Python

honggang_io

import re
while True:
    try:
        re_str = input()
        s = input()

        li = re.findall(re_str.replace('?','.?').replace('*','.*'), s)
        print('true' if len(li)>0 else 'false')
    except:
        break

发表于 2020-03-19 00:14:08 回复(0)

Python

朝夕_

import re
while True:
  try:
    a,b = input().strip(),input().strip()
    a = a.replace("?","\w{1}").replace(".","\.").replace("*","\w*")
    c = re.findall(a,b)
    if b in c and len(c) == 1:
      print("true")
    else:
      print("false")
  except:
    break

发表于 2020-02-22 12:22:46 回复(8)

Python

St_Jimi

def check(a,b):
    for i in range(len(a)):
        if a[i]==b[i]:
            pass
        elif a[i]=='?':
            pass
        elif a[i]=='*':
            if i+1<len(a[i]):
                for j in range(len(b[i+1:])):
                    if b[j]==a[i+1]:
                        return(b[j+1:])
        else:
            return False
    return True
while True:
try:
x=input()
y=input()
print(str(check(x,y)).lower())
except:
break

发表于 2020-02-09 21:36:24 回复(0)

Python

cyd1310997

import re
while True:
    try:
        a = '^' + input().replace('*', '\w*').replace('?', '\w?') + '$'
        b = input()
        print('true') if re.match(a, b) else print('false')
    except: break

发表于 2019-08-21 22:47:22 回复(0)

Python

lx的流星

import re
while True:
    try:
        inp = input().strip()
        strs = input().strip()
        #print(strs)
        inp = inp.replace("?", "\w{1}").replace("*","\w{0,}")
        pattern = re.findall(inp,strs)
        #match = pattern.match(strs)
        if len(pattern)==1 and pattern[0]==strs:
            print('true')
        else:
            print('false')

    except:
        break;

发表于 2019-07-12 10:36:31 回复(0)

Python

CassielLee

/*递归解法，假设string1是带有通配符的字符串，string2是要匹配的字符串，在第i个字符处有三种
情况：
   1、两个字符串都是字母的时候，不相等就是false;
   2、遇到?通配符的时候，跳过第i个字符，继续匹配从string1[i+1]，string2[i+1]开始匹配；
   3、遇到“*”通配符，则遍历后面的字符串，根据情况在进行判断；
*/
def isMatch(string1, string2):
    for i in range(len(string1)):
        if string1[i].isalpha():
            if string1[i] != string2[i]:
                return 'false'
        else:
            if string1[i] == "?":
                isMatch(string1[i + 1:], string2[i + 1:])
            elif string1[i] == "*":
                for j in range(i + 1, len(string1)):
                    if string1[j] == '?' or string1 == "*":
                        isMatch(string1[j:], string2[j:])
                    elif string1[j].isalpha() and string2.isalpha():
                        if string1[j] == string2[j]:
                            isMatch(string1[j:], string2[j:])
    return 'true'

while True:
    try:
        string1 = input()
        string2 = input()
        print(isMatch(string1, string2))
    except:
        break

发表于 2018-09-03 16:30:45 回复(1)

Python

questRush

import re
try:
	while 1:
		pattern, s = raw_input(), raw_input()
		pattern = pattern.replace('.', '\\.').replace('?', '.').replace('*', '[0-9A-z]*')
		a = re.findall(pattern, s)
		print str(bool(len(a) == 1 and a[0] == s)).lower()
except:
	pass

发表于 2017-02-15 22:57:20 回复(1)

提交观点

问题信息

字符串

难度：

20条回答 2959收藏 36082浏览

通过挑战的用户

查看代码

猪儿拱

2023-02-26 22:43:42
帅阿衰

2023-01-08 10:20:13
hnSS

2023-01-02 16:02:27
芊樱烛渊

2022-10-30 20:15:16
牛客39961...

2022-10-30 10:33:48

字符串通配符

输入描述:

输出描述:

输入

输出

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题