首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符
  • 热度指数：173531 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。

输入：
通配符表达式；
一组字符串。

输出：

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：
进阶：时间复杂度：，空间复杂度：

输入描述:
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串


输出描述:
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
示例1

输入

te?t*.*
txt12.xls

输出

false
示例2

输入

z
zz

输出

false
示例3

输入

pq
pppq

输出

false
示例4

输入

**Z
0QZz

输出

true
示例5

输入

?*Bc*?
abcd

输出

true
示例6

输入

h*?*a
h#a

输出

false

说明

根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false
示例7

输入

p*p*qp**pq*p**p***ppq
pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp

输出

false
算法知识视频讲解
添加回答
Python
牛客590711274号头像 牛客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号头像 牛客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头像 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头像 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，比较这些非法字符是否一样，不一样直接退出。
再对分割后的子串进行通配符比较。

编辑于 2020-07-30 22:02:50 回复(0)
Python
君临天下201804050931706头像 君临天下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头像 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头像 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头像 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头像 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的流星头像 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头像 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头像 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条回答 35003浏览

热门推荐

通过挑战的用户

查看代码

相关试题

字符串通配符

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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