[leetcode]10.|[leetcode]10. Regular Expression Matching [leetcode]10.RegularExpressionMatchi

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and ''.
'.' Matches any single character.
'' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

这题是用一个带和的 pattern 去 match 一个string. 并且要求 pattern 要覆盖string ,也就是说 pattern 为‘ab’ , string 为‘ababab’ 是不行的。
这里我们采用动态规划的方法
dp[i][j] 表示 p[:i] 与 s[:j]是否match , match为1 otherwise 0.
1 . 处理边界情况（s 或 p 为空）

if (i==0 and j==0) or (p[i]=="*" and dp[i-2][j]): dp[i][j] = 1

[leetcode]10.|[leetcode]10. Regular Expression Matching

文章图片
image.png 2. 两边当前字符直接相等这个比较容易想到，有点类似最长公共子序列。
当你s[j] ==p[i] 的时候，只要看dp[i-1][j-1] 是否为1
这里我们要注意 match 还包括 p[i] =="." 的情况。

if p[i] == s[j] or p[i] ==".": dp[i][j] = dp[i-1][j-1]

文章图片
image.png 3. 单独处理 p[i] =="*" 的情况这题难点就在这个“*”
他表示 0个和表示 >=1 个是2种不同的作用。

0 个表示他把当前p 下标 i-1的字符(上一个字符) 吃掉了 (类似 “abc* == ab”)，所以当前的p [:i] 等价于 p[:i-2], 所以当前状态等同于 dp[i-2][j] 是的状态
1 表示可以为‘b’,'bb'.. 无穷多个.
所以这里我们暂时不考虑 s[j] 的情况，我们先看dp[i][j-1] 也就是下图粉色标注的‘ab’, 'a.d*' 即 s[:j-1] 与p[:i] 的match 状态。
如果 match, 就表面 s[:j-1] 和p[:i] 不仅match , 而且p[:i] 还可以重复号前的那个元素p[i-1] !
因此，我们只要确保当前的s[j] 与 p[i-1] match 就好了。

ifp[i]=="*": if dp[i-2][j]: dp[i][j] = 1 if dp[i][j-1] and (p[i-1] == s[j] or p[i-1] == "."): dp[i][j] =1

文章图片
image.png 代码 【[leetcode]10.|[leetcode]10. Regular Expression Matching】这里用python 写了一下

class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ s='0'+s p='0'+p dp= [ [0 for col in range(len(s))] for row in range(len(p))]for i in range(len(p)): for j in range(len(s)): # 初始化边界 if i==0 or j==0: # 1. dp[0][0] : "" match "" --> True # 2. p[i] =="*" if dp[i-2][j] == True --> True if (i==0 and j==0) or (p[i]=="*" and dp[i-2][j]): dp[i][j] = 1 else: # 1. 当前 2点相等检查 dp[i-1][j-1] if p[i] == s[j] or p[i] ==".": dp[i][j] = dp[i-1][j-1] continue # p = "*" # 1. * 代表0 --> dp[i-2][j] # 2. * 代表1 ...nif dp[i][j-1] ==True +p[i-1] ==s[j] --> True ifp[i]=="*": if dp[i-2][j]: dp[i][j] = 1 if dp[i][j-1] and (p[i-1] == s[j] or p[i-1] == "."): dp[i][j] =1for _ in dp: print(_)return True if dp[-1][-1] else Falseif __name__ =="__main__": sol = Solution() print(sol.isMatch("aab","c*a*b"))[1, 0, 0, 0] [0, 0, 0, 0] [1, 0, 0, 0] [0, 1, 0, 0] [1, 1, 1, 0] [0, 0, 0, 1] True