题解 | #字符串通配符#动态规划空间只需O(n)

import sys
match = sys.stdin.readline().strip().lower()
s = sys.stdin.readline().strip().lower()
cur = [True]+[False for _ in range(len(s))] #此时的cur代表match为空时，与string中每一位的匹配，其中[True]代表match和string都为空时匹配成功

for i in range(len(match)):
    pre = cur 
    cur = [False for _ in range(len(s)+1)]
    cur[0] = True if pre[0]==True and match[i]=='*' else False
    for j in range(0,len(s)):
        if pre[j] and (match[i] == s[j] or ((match[i]=='?' or match[i]=='*') and (s[j].isalpha() or s[j].isdigit()))):
            cur[j+1] = True
        elif (pre[j+1] or cur[j]) and match[i]=='*' and (s[j].isalpha() or s[j].isdigit()):
            cur[j+1] = True
print(str(cur[-1]).lower())