题解 | #字符串通配符#

'''
这题采用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