Python中的通配符匹配

假设我们有一个输入字符串s和另一个输入字符串p。这是主字符串，p是模式。我们必须定义一种方法，该方法可以匹配字符串中的模式。因此，我们必须针对支持“？”之类的通配符的正则表达式实现此功能。还有“ *”。

• 点'？' 匹配任何单个字符

• 星号“ *”匹配零个或多个字符。

因此，例如，如果输入像s =“ aa”和p =“ a？”，则为true，对于相同的输入字符串，如果模式为“？*”，则为true。

为了解决这个问题，我们将遵循以下步骤-

• ss：= s和ps的大小：= p的大小

• 使dp成为ss x ps大小的矩阵，并使用假值填充它

• 通过在这些之前添加一个空格来更新p和s

• 对于范围在1到ps之间的i-

• dp [0，i]：= dp [0，i-1]

• 如果p [i] =星，则

• 对于我在1到ss范围内

• 如果s [i]是p [j]或p [j]是'？'，则

• 否则，当p [j]为星号时，则

• dp [i，j]：= dp [i – 1，j – 1]

• dp [i，j]：= dp [i – 1，j]和dp [i，j – 1]的最大值

• 对于1到ps范围内的j

• 返回dp [ss，ps]

范例(Python)

让我们看下面的实现以更好地理解-

class Solution(object):
   def isMatch(self, s, p):
      sl = len(s)
      pl = len(p)
      dp = [[False for i in range(pl+1)] for j in range(sl+1)]
      s = " "+s
      p = " "+p
      dp[0][0]=True
      for i in range(1,pl+1):
         if p[i] == '*':
            dp[0][i] = dp[0][i-1]
      for i in range(1,sl+1):
         for j in range(1,pl+1):
            if s[i] == p[j] or p[j] == '?':
               dp[i][j] = dp[i-1][j-1]
            elif p[j]=='*':
               dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      return dp[sl][pl]
ob = Solution()print(ob.isMatch("aa", "a?"))
print(ob.isMatch("aaaaaa", "a*"))

输入项

"aa", "a."
"aaaaaa", "a*"

输出结果

True
True