假设我们有一个输入字符串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