题解 | #字符串通配符#
字符串通配符
http://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
'''
这题采用bp表格去做实在过于巧妙
纵向是带有通配符的字符串matching(m)，横向是需要匹配的字符串str1(s)，表格中的值是布尔值
bp表格中第0行所有列与第0列所有行的值均可以提前判断出
每个表格中其他空格有四种情况，一行一行的更新：
1、matching[i-1].lower()==str1[j-1].lower()时：bp[i][j]=bp[i-1][j-1]
2、matching[i-1].lower()!=str1[j-1].lower()时：bp[i][j]=False
3、m[i-1]=='?' and s[j-1].isalnum()时：bp[i][j]=bp[i-1][j-1]
4、m[i-1]=='*'时：bp[i][j]=bp[i-1][j] or bp[i][j-1]
while True:
try:
matching=input()
str1=input()
# 创建初始值全是False的bp表格
bp=[[False for _ in range(len(str1)+1)] for _ in range(len(matching)+1)]
# 更新可以提前判断的参数，方便后面迭代更新
bp[0][0]=True
for i in range(1,len(matching)+1):
if matching[i-1]=='?' or matching[i-1]=='*':
bp[i][0]=True
else:
break
# 可以提前判断的参数已经更新完成，现在迭代更新表格中的其他值
for i in range(1,len(matching)+1):
for j in range(1,len(str1)+1):
if matching[i-1].lower()==str1[j-1].lower():# 注意不区分大小写
bp[i][j]=bp[i-1][j-1]
elif matching[i-1]=='?' and str1[j-1].isalnum():
bp[i][j]=bp[i-1][j-1]
elif matching[i-1]=='*':
bp[i][j]=bp[i-1][j] or bp[i][j-1]
if bp[len(matching)][len(str1)]:
print('true')
else:
print('false')
except:
break
这题采用bp表格去做实在过于巧妙
纵向是带有通配符的字符串matching(m)，横向是需要匹配的字符串str1(s)，表格中的值是布尔值
bp表格中第0行所有列与第0列所有行的值均可以提前判断出
每个表格中其他空格有四种情况，一行一行的更新：
1、matching[i-1].lower()==str1[j-1].lower()时：bp[i][j]=bp[i-1][j-1]
2、matching[i-1].lower()!=str1[j-1].lower()时：bp[i][j]=False
3、m[i-1]=='?' and s[j-1].isalnum()时：bp[i][j]=bp[i-1][j-1]
4、m[i-1]=='*'时：bp[i][j]=bp[i-1][j] or bp[i][j-1]
'''
while True:
try:
matching=input()
str1=input()
# 创建初始值全是False的bp表格
bp=[[False for _ in range(len(str1)+1)] for _ in range(len(matching)+1)]
# 更新可以提前判断的参数，方便后面迭代更新
bp[0][0]=True
for i in range(1,len(matching)+1):
if matching[i-1]=='?' or matching[i-1]=='*':
bp[i][0]=True
else:
break
# 可以提前判断的参数已经更新完成，现在迭代更新表格中的其他值
for i in range(1,len(matching)+1):
for j in range(1,len(str1)+1):
if matching[i-1].lower()==str1[j-1].lower():# 注意不区分大小写
bp[i][j]=bp[i-1][j-1]
elif matching[i-1]=='?' and str1[j-1].isalnum():
bp[i][j]=bp[i-1][j-1]
elif matching[i-1]=='*':
bp[i][j]=bp[i-1][j] or bp[i][j-1]
if bp[len(matching)][len(str1)]:
print('true')
else:
print('false')
except:
break
【牛客站内】华为机试题—中等 文章被收录于专栏
【牛客站内】华为机试题练习记录
查看8道真题和解析
