题解 | #字符串通配符 leetcode10动态规划 #

'''
整体思路和leetcode 10. 一样，
唯一要小心的是 *号虽然不能匹配非数字和字母之外的字符，
但是可以通过0次匹配来兼容包含这种一场字符，
比如例子： 
reg = 't?t*1*.*'
tgt = 'txt12.xls'
'''
reg = input().strip().lower()
tgt = input().lower()

reg_len = len(reg)
tgt_len = len(tgt)
dot = '?'
star = '*'

dp_arr = [ [False] * (reg_len+1) for i in range(tgt_len + 1)]

dp_arr[0][0] = True

def can_match(a):
    a_lower = a.lower()
    return (a_lower>='a' and a_lower<='z') or (a_lower >='0' and a_lower <='9')

def is_matcher(a):
    a_lower = a.lower()
    return a_lower == dot or a_lower == star

for i in range(1, reg_len+1):
    if reg[i-1] in [dot, star]:
        dp_arr[0][i] = dp_arr[0][i-1]

for i in range(0, tgt_len):
    idx = i+1
    for j in range(0, reg_len):
        jdx = j+1
		# 正则串目前位置是普通字符，直接普通匹配
        if not is_matcher(reg[j]):
            if reg[j] == tgt[i]:
                dp_arr[idx][jdx] = dp_arr[idx-1][jdx-1]
		# 正则串目前是通配符，开始细分条件判断
        else:
		  	#关键点！ 即便当前的目标串字符是异常字符，但是->
			# *号通配符可以通过0次匹配来兼容，不能跳过
            if not can_match(tgt[i]):
                if reg[j] != star:
                    continue
            #核心dp转移公式，详细参考leetcode No.10
            if reg[j] == star:
                dp_arr[idx][jdx] = dp_arr[idx-1][jdx] or dp_arr[idx][jdx-1]
            else:
                dp_arr[idx][jdx] = dp_arr[idx-1][jdx-1]
       
if dp_arr[tgt_len][reg_len]:
    print('true')
else:
    print('false')