题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
方法：动态规划
思路：
1、定义dp[i][j]为p[0:j]是否匹配s[0:i]的二维数组，匹配为1，不匹配为0
2、初始值 dp[0][0]=1，因为空字符可以匹配空字符，dp[i][0]全部为0，因为
p为空的话无法匹配非空字符s，dp[0][j]=dp[0][j-1]，因为只有 * 才有可能匹配
空字符，初始值设置完成。
3、状态转移方程：当p[j-1]=s[i-1]时，dp[i][j]取决于dp[i-1][j-1]，因为如果j-1之前
的p和i-1之前的s可以匹配的话，那么j-1的p就可以匹配i-1的s；当 p[j-1]='?' 时，如果
s[i-1]不为特殊符号，则同上；当 p[j-1]= '*' 时，这里需要判断s[i-1]是否为特殊符号，
不是的话可以用*也可以不用，是特殊符号就只能不用了，若s[i-1]不为特殊符号，
则dp[i][j] = dp[i-1][j] or dp[i][j-1]，因为第i个字母可以直接用来匹配 * ，所以看第i个
字母前面的就行，若s[i-1]为特殊符号 dp[i][j] = dp[i][j-1]，排除掉 * ，看 * 前面的p是否
能够匹配s就可以了
def regex():
p = input()
s = input()
n,m = len(p),len(s)
dp = [[0]*(n+1) for _ in range(m+1)]
dp[0][0] = 1
for j in range(1,n+1):
if p[j-1]=='*':
dp[0][j] = dp[0][j-1]
for i in range(1,m+1):
for j in range(1,n+1):
if p[j-1]=='*':
if '0'<=s[i-1]<='9' or 'a'<=s[i-1]<='z':
dp[i][j]=dp[i-1][j] or dp[i][j-1]
else:
dp[i][j]=dp[i][j-1]
elif p[j-1]=='?':
if '0'<=s[i-1]<='9' or 'a'<=s[i-1]<='z':
dp[i][j]=dp[i-1][j-1]
elif p[j-1].lower()==s[i-1].lower():
dp[i][j]=dp[i-1][j-1]
if dp[m][n]:
print('true')
else:
print('false')
regex()