递归/正则匹配 | HJ71 字符串通配符

# 最优解1
import re
while 1:
    try:
        p = input().lower()
        s = input().lower()
        p = p.replace('?', '[a-z0-9]{1}').replace('*', '[a-z0-9]*').replace('.', '\.')
        if s in re.findall(p, s):
            print('true')
        else:
            print('false')
    except:
        break


# 最优解2
p = input().lower()
s = input().lower()
def func(p, s):
    if s == '':  # 字符串遍历完
        if p == '' or p.replace('*', '')=='':
            return True
        else:
            return False
    elif p == '':  # 字符串未遍历完且没有匹配码
        return False
    else:
        if p[-1] == s[-1] or (p[-1]=='?' and s.isalnum()):
            return func(p[:-1], s[:-1])
        elif p[-1] == '*':
            return func(p[:-1], s) or func(p, s[:-1])
        else:
            return False
    
if func(p, s):
    print('true')
else:
    print('false')

用时：2h

注意：

1、不区分字母大小写时，提早将pattern匹配模板与s字符串都转为小写

2、递归返回情况：

s字符串为空：p模板也为空或p中只剩 *，返回True，否则返回False

s字符串不为空：p模板为空时匹配失败返回False

3、？与 *只能匹配字母或数字，用 isalnum()函数

4、p模板中有*：两种走法，有一条通过即可

A. 剥掉 *继续递归

B. 保留 *且匹配去掉s的一个字符，继续进入递归；进入递归后仍会走到*号判断，又会有剥掉*进入下一递归，使得*可以一直保留到之后的某层递归（在该递归中剥掉*后剩余p模板与s字符串可完全匹配。参考调试p=efg*abc，s=efgddabc）