Regular Expression Matching（DP）

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 theentireinput 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

  *

  .

Example 1:

Input:

s = "aa"
p = "a"

Output:
 false

Explanation:
 "a" does not match the entire string "aa".

Example 2:

Input:

s = "aa"
p = "a*"

Output:
 true

Explanation:
 '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:

s = "ab"
p = ".*"

Output:
 true

Explanation:
 ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:

s = "aab"
p = "c*a*b"

Output:
 true

Explanation:
 c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:

s = "mississippi"
p = "mis*is*p*."

Output:
 false

分析

1可以顺序等得话 f[i][j] = f[i-1][j-1]

2不能的话需要*

a.把a*当做空串：f[0][j] = f[0][j-2]

b. 让s最后的字符有保障之后：if s[i-1] == p[j-2] or p[j-2] == '.' 让P匹配好s前面所有的：f[i][j] = f[i-1][j]

dp

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        sl = len(s)
        pl = len(p)
        f = [[False]*(pl+1) for _ in range(sl+1)]
        f[0][0] = True

        for j in range(1,pl+1):
            if p[j-1] == '*':
                f[0][j] = f[0][j-2]

        for i in range(1,sl+1):
            for j in range(1,pl+1):
                if s[i-1] == p[j-1] or p[j-1] == '.':
                    f[i][j] = f[i-1][j-1]
                elif p[j-1] == '*':
                    if f[i][j-2]:
                        f[i][j] = True
                    elif s[i-1] == p[j-2] or p[j-2] == '.':
                        f[i][j] = f[i-1][j]

        return f[sl][pl]

recursive

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if not s and not p:
            return True
        return self.helper(s,p,len(s)-1, len(p)-1) #倒着来
    def helper(self,s,p,i,j):
        if i==-1 and j==-1: #相当于i==pos
            return True
        if j<0:#这里有查j所以下面只要查i
            return i<0

        if p[j] == '*':
            return i>=0 and (s[i]==p[j-1] or p[j-1]=='.') and self.helper(s,p,i-1,j) or self.helper(s,p,i,j-2) #前面i-1所以要查i，后面直接I所以不用
        else:
            return i >= 0 and (s[i] == p[j] or p[j] == '.') and self.helper(s, p, i - 1, j-1)#前面i-1所以要查i