Python 中的正则表达式匹配

pythonserver side programmingprogramming更新于 2026/1/15 3:56:17

假设我们有一个输入字符串 s 和另一个输入字符串 p。这里 s 是主字符串，p 是模式。我们必须定义一个可以匹配字符串中模式的方法。所以我们必须为支持 ‘.’ 和 ‘*’ 的正则表达式实现这个方法。

点 ‘.’ 匹配任何单个字符
星号 ‘*’ 匹配零个或多个前面的元素。

例如，如果输入像 s = “aa”并且 p = “a.”，那么它将为真，对于相同的输入字符串，如果模式是 “.*”，那么它将为真。

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

ss := s 的大小和 ps := p 的大小
使 dp 成为大小为 ss x ps 的矩阵，并使用 false 值填充它
通过在它们之前添加一个空格来更新 p 和 s
对于 2 到 ps 范围内的 i −
- 当 p[i] 为星号时，dp[0, i] := dp[0, i - 2]，否则错误
对于范围为 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] 的最大值
return 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*"))