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+ 次瀏覽

啟動您的 職業生涯

完成課程獲得認證

開始學習
廣告