题解 | #字符串通配符# 接着动规接着舞

def match(pattern, string):
    m = len(pattern)
    n = len(string)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(1, m + 1):
        if pattern[i - 1] == '*':
            dp[i][0] = dp[i - 1][0]
        else:
            break
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if pattern[i - 1] == '*':
                dp[i][j] = dp[i - 1][j] or (dp[i][j - 1] and string[j - 1].isalnum())
            elif (pattern[i - 1] == '?' and string[j - 1].isalnum()) or pattern[i - 1] == string[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]

reg = input().lower()
string = input().lower()
if match(reg, string):
    print('true')
else:
    print('false')

这种前面对后面一票否决的多米诺骨牌，动态规划就对了。

思路图解参考HJ52 计算字符串的编辑距离 @南江边 的题解：https://blog.nowcoder.net/n/e9e179e429324eaa839d296c618f1de5

时间复杂度O(mn)；空间复杂度O(mn)，可优化至O(n)。

def match(pattern, string):
    m = len(pattern)
    n = len(string)
    prev_row = [False] * (n + 1)
    curr_row = [False] * (n + 1)
    prev_row[0] = True
    for i in range(1, m + 1):
        curr_row[0] = prev_row[0] if pattern[i - 1] == '*' else False
        for j in range(1, n + 1):
            if pattern[i - 1] == '*':
                curr_row[j] = prev_row[j] or (curr_row[j - 1] and string[j - 1].isalnum())
            elif (pattern[i - 1] == '?' and string[j - 1].isalnum()) or pattern[i - 1] == string[j - 1]:
                curr_row[j] = prev_row[j - 1]
        prev_row = curr_row
    return prev_row[n]

reg = input().lower()
string = input().lower()
if match(reg, string):
    print('true')
else:
    print('false')