题解 | #字符串通配符#

借鉴了各种大佬的解法，总结了三种解法，前两种思路是一样的

p为通配符表达式 s是为字符串

1，当p 和 s都为空时： ture

2，当p等于空，s不为空： false

3 ，当p不为空，s为空时：

1，p里面字符全都是“*”：true

2，p里面字符含有除“*”以外的字符 ： false

4，当p，s都不为空时，分为以下几种：

1，当p[m-1]=="*"

1,s[n-1]是数字或者字母(用isalnum()判断）：

2s[n-1]不是数字或者字母：

2，当p[m-1]=="?" 并且s[n-1]是数字或者字母时：

3，当p[m-1]..lower()==s[n-1].lower()

具体代码如下：

一 递归：

def func(p,s):
    m,n=len(p),len(s)
    if p==''and s=='':
        return True
    elif p=='' and s!='':
        return False
    elif p!='' and s=='':
        if p.replace("*",'')=='':
            return True
        else:
            return False
    else:
        if p[m-1]=="*":
            if s[n-1].isalnum():#必须进行讨论，不然像tx#*.* tx#t.zxy这种程序会返回false
                return func(p,s[:n-1]) or func(p[:m-1],s)
            else:
                return  func(p[:m-1],s)
        elif p[m-1]=="?" and s[n-1].isalnum():
            return func(p[:m-1],s[:n-1])
        elif p[m-1].lower()==s[n-1].lower():
            return func(p[:m-1],s[:n-1])
        else:
            return False
p=input()
s=input()
while True:
    try:
        if func(p,s):
            print("true")
        else:
            print("false")
    except:
        break

二，动态规划法

while True:
    try:
        p,s=input(),input()
        m,n=len(p),len(s)
        dp=[[False for _ in range(n+1)]for _ in range(m+1)]
        #定义dp[i][j]为p[0:i]是否匹配s[0:j]的二维数组
        dp[0][0]=True
        for i in range(1,m+1):
            if p[i-1]=="*":
                dp[i][0]=dp[i-1][0]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[i-1]=="*":
                    if s[j-1].isalnum():
                        dp[i][j]=dp[i-1][j] or dp[i][j-1]
                    else:
                        dp[i][j]=dp[i-1][j]
                elif p[i-1]=="?" and s[j-1].isalnum():
                    dp[i][j] = dp[i-1][j-1]
                elif p[i-1].lower()==s[j-1].lower():
                    dp[i][j]=dp[i-1][j-1]
        if dp[m][n]:
            print("true")
        else:
            print("false")
    except:
        break

三，正则表达式

import re
while True:
    try:
        # 依题意，能被*和?匹配的字符仅由英文字母和数字0到9组成，即对应[a-zA-Z0-9]
        # 在re的pattern种，“.”表示的全匹配(任何字符)，所以需要先转义
        # ？ 表示匹配一个字符，而re的pattern的"？"表示0或1次，所以要直接使用[a-zA-Z0-9]替换
        # * 表示匹配0或多个，和re的pattern的"*"意思一致，所以可以只用[a-zA-Z0-9]*来替换
        p,s=input(),input()
        p=p.replace(".","\.").replace("?","[a-zA-Z0-9]").replace("*","[a-zA-Z0-9]*")
        if s in re.findall(p,s,re.I): # 因为用到了re.I（不区分大小写），所以上面就算直接使用[A-Z0-9]或[a-z0-9]也是一样的效果
            print("true")
        else:
            print("false")
    except:
        break