[leetcode]10. Regular Expression

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

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 就好了。

 if  p[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

代码

这里用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 ...n  if dp[i][j-1] ==True +  p[i-1] ==s[j] --> True
                    if  p[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

        for _ in dp:
            print(_)

        return True if dp[-1][-1] else False
        

if __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

image.png