Pythonでの正規表現マッチング

• ドット「。」は任意の1文字に一致します

• スター「*」は、前の要素の0個以上に一致します。

したがって、たとえば、入力がs =“ aa”およびp =“ a。”の場合、それはtrueになります。同じ入力文字列に対して、パターンが“。*”の場合、trueになります。

これを解決するには、次の手順に従います-

• ss：=sのサイズとps：=pのサイズ

• dpをサイズssxpsの行列にし、false値を使用してこれを埋めます

• これらの前に1つの空白スペースを追加して、pとsを更新します

• 2からpsの範囲のiの場合-

  • dp [0、i]：=dp [0、i-2]（p [i]がスターの場合、それ以外の場合はFalse

• 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、j-2]

      • s[i]がp[j– 1]であるか、p [j – 1]がドットである場合、

        • dp [i、j]：=dp [i、j]とdp [i – 1、j]の最大値

• dp [ss、ps]

  を返します

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

True
True