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

  `*`

  .

**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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/facebook/regular-expression-matchingdp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.