首页 > 试题广场 >

字符串匹配问题

[编程题]字符串匹配问题

热度指数：2495 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对于字符串str，其中绝对不含有字符’.’和‘*’。再给定字符串exp，其中可以含有’.’或’‘*’，’*’字符不能是exp的首字符，并且任意两个’*‘字符不相邻。exp中的’.’代表任何一个字符，exp中的’*’表示’*‘的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配(注意：输入的数据不保证合法，但只含小写字母和‘.’和‘*’)。

输入描述:

输入包含两行，两个字符串，分别代表str和exp。

输出描述:

如果str是能被exp匹配，请输出“YES”，否则输出“NO”。

示例1

输入

abc
abc

输出

YES

示例2

输入

abcd
.*

输出

YES

备注:

时间复杂度,额外空间复杂度,(n为字符串str长度，m为字符串exp长度)

算法知识视频讲解

Python

牛客157007370号

def buhefa(s):
if s[0]=='*':
return 1
for i in range(len(s)-1):
if s[i]=='*' and s[i+1]=='*':
return 1
return 0

def quchong(exp):
i=0
while i<len(exp)-2:
if exp[i+1]=='*' and exp[i]==exp[i+2]:
exp=exp[:i+2]+exp[i+3:]
else:
i+=1

def solve(s,exp):
flag=0
if buhefa(exp):
return 0
else:
i,j=0,0
while i<len(s) and j<len(exp):
if j<len(exp)-1 and exp[j+1]=='*':
if exp[j]=='.':
if j+2==len(exp):
break
else:
j+=2
while i<len(s) and s[i]!=exp[j]:
i+=1
i_bianli=i+1
while i_bianli<len(s):
if solve(s[i_bianli:],exp[j:]):
return 1
i_bianli+=1

else:
while i<len(s) and s[i]!=exp[j]:
i+=1
j+=2
else:
if exp[j]==s[i] or exp[j]=='.':
i+=1
j+=1
else:
return 0
flag=1
break
if flag==0:
return 1

s=input()
exp=input()
flag=solve(s,exp)
if flag:
print('YES')
else:
print('NO')

发表于 2020-03-20 10:19:38 回复(0)