题解 | #字符串通配符# 递归的完全解

import sys
import re

A = input().lower()
B = input().lower()
mem = {}

def match(rule_index: int, string_index: int):

    if (rule_index,string_index) in mem: 
        return mem[(rule_index,string_index)]

    rule,string = A[rule_index:], B[string_index:]

    if not rule and not string:
        mem[(rule_index,string_index)] = True
        return True

    if not rule and string:
        mem[(rule_index,string_index)] = False
        return False

    if rule and not string:
        if set(rule) == {'*'}:
            mem[(rule_index,string_index)] = True
            return True
        mem[(rule_index,string_index)] = False
        return False

    
    if rule == '*' and string.isalnum():
        mem[(rule_index,string_index)] = True
        return True
        
    result = False
    if rule[0] == string[0] or (rule[0] == '?' and string[0].isalnum()): 
        result = match(rule_index+1,string_index+1)

    if rule[0] == '*':
        result = match(rule_index+1,string_index) or match(rule_index,string_index+1)
    
    mem[(rule_index,string_index)] = result  
    return result



print(str(match(0,0)).lower())

这道题目最好是用动态规划来做，如果要用递归的话，需要使用一个字典来保存已有的结果来减少计算次数（其实等价于动态规划）