题解 | #字符串通配符#

字符串通配符

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

【牛客站内】华为机试题练习记录

全部评论
print('tql')
1 回复 分享
发布于 2023-04-18 22:21 江苏

相关推荐

点赞 评论 收藏
分享
5 1 评论
分享
牛客网
牛客企业服务