题解 | #字符串通配符#
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
def match(p, s):
m, n = len(p), len(s) #m是正则字符串，dp表中竖直放
'''
初始化边界：
1、dp[0][0] = True，空模式空字符串，匹配成功；
2、dp[0][j] = False，空模式无法匹配非空字符串；
3、dp[i][0]不确定，只有模式为星号*时，才能匹配空字符串，即模式p前i个字符均为星号*。
'''
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for i in range(1, m+1): #遍历正则字符串，一行一行,即模式p前i个字符均为星号*
if p[i-1] == '*':
dp[i][0] = True
else:
break #只要遍历到非*则退出
# print(dp)
for i in range(1, m+1):
for j in range(1, n+1):
if p[i-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1] #有1则1 1 or 0 =1
elif p[i-1] == '?' and s[j-1].isalnum():
dp[i][j] = dp[i-1][j-1]
elif s[j-1].lower() == p[i-1].lower():
dp[i][j] = dp[i-1][j-1]
return dp[m][n]
while True:
try:
pattern, string = input(), input()
if match(pattern, string):
print('true')
else:
print('false')
except:
break
m, n = len(p), len(s) #m是正则字符串，dp表中竖直放
'''
初始化边界：
1、dp[0][0] = True，空模式空字符串，匹配成功；
2、dp[0][j] = False，空模式无法匹配非空字符串；
3、dp[i][0]不确定，只有模式为星号*时，才能匹配空字符串，即模式p前i个字符均为星号*。
'''
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for i in range(1, m+1): #遍历正则字符串，一行一行,即模式p前i个字符均为星号*
if p[i-1] == '*':
dp[i][0] = True
else:
break #只要遍历到非*则退出
# print(dp)
for i in range(1, m+1):
for j in range(1, n+1):
if p[i-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1] #有1则1 1 or 0 =1
elif p[i-1] == '?' and s[j-1].isalnum():
dp[i][j] = dp[i-1][j-1]
elif s[j-1].lower() == p[i-1].lower():
dp[i][j] = dp[i-1][j-1]
return dp[m][n]
while True:
try:
pattern, string = input(), input()
if match(pattern, string):
print('true')
else:
print('false')
except:
break
合合信息公司福利 236人发布
查看21道真题和解析