Python中的正则表达式匹配

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

点。匹配任何单个字符

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

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

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

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

使dp成为ssxps大小的矩阵，并使用假值填充它

通过在这些之前添加一个空格来更新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