Python中的正则表达式匹配

  • Z时代
  • 2024-01-10
  • 分类：综合

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

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

  • 星号“ *”匹配零个或多个前一个元素。

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

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

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

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

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

  • 对于i在2到ps范围内-

    • dp [0，i]：= dp [0，i-2]当p [i]为星型时，否则为False

  • 对于我在1到ss范围内

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

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

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

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

    • dp [i，j]：= dp [i，j-2]

    • 如果s [i]是p [j – 1]或p [j – 1]是点，则

    • 适用于1至ps范围内的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

    以上是 Python中的正则表达式匹配 的全部内容， 来源链接： utcz.com/z/331579.html

    回到顶部