Python中的通配符匹配

假设我们有一个输入字符串 s 和另一个输入字符串 p。这里 s 是主字符串，p 是模式。我们必须定义一个方法，能够在字符串中匹配模式。所以我们必须为支持像“？”和“*”这样的通配符的正则表达式实现它。

  • 点“？”匹配任何单个字符

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

例如，如果输入类似于 s = “aa” 和 p = “a?”，则结果为真；对于相同的输入字符串，如果模式是“?*”，则结果也为真。

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

  • ss := s 的大小，ps := p 的大小

  • 创建一个大小为 ss x ps 的 dp 矩阵，并使用 false 值填充它

  • 在这些字符串之前添加一个空格来更新 p 和 s

  • 对于范围 1 到 ps 中的 i：

    • 如果 p[i] 为星号，则

      • dp[0, i] := dp[0, i - 1]

  • 对于范围 1 到 ss 中的 i

    • 对于范围 1 到 ps 中的 j

      • 如果 s[i] 等于 p[j]，或者 p[j] 为“？”，则

        • dp[i, j] := dp[i – 1, j – 1]

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

        • dp[i, j] := dp[i – 1, j] 和 dp[i, j – 1] 的最大值

  • 返回 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

更新于：2020年5月26日

4K+ 次浏览

启动您的 职业生涯

完成课程获得认证

开始学习
广告