题解 | Python #正则表达式匹配#

每次这种很多条件的动态规划还是习惯用dfs做 lol

from functools import cache
s1 = input()
s2 = input()
@cache
def dfs(i,j):
    if i==0 and j!=0:
        if s2[j-1]=='*':
            return dfs(i,j-2)
        return False
    if i!=0 and j==0: return False
    if i==0 and j==0: return True

    if s2[j-1]=='.' or s1[i-1]==s2[j-1]:
        return dfs(i-1,j-1)
    elif s2[j-1]=='*':
        if dfs(i,j-2):
            return True
        if s2[j-2] == s1[i-1] or s2[j-2]=='.':
            return dfs(i-1,j)

if dfs(len(s1),len(s2)):
    print('true')
else:
    print('false')