# \[10]\[困难]\[动态规划] 正则表达式匹配

## 题目描述

[10. 正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching/) [剑指 Offer 19. 正则表达式匹配](https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/)

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '\*' 的正则表达式匹配。

'.' 匹配任意单个字符 '\*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。 示例 1:

```
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
```

示例 2:

```
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
```

示例 3:

```
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
```

示例 4:

```
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
```

示例 5:

```
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
```

## 解题思路

### 动态规划

状态的定义比较直观, `dp[i][j]`表示字符串`s`的前`i`个字符能否与模式串`p`的前`j`个字符匹配.

状态转移方程有些麻烦. 可以看出`*`字符是特殊的字符, 需要以`p[j] == '*'`与否, 分别讨论.

**p\[j]不为\***

如果`p[j] == '.'`, 那么可以与任何一个字符匹配, 因此有`dp[i][j] = dp[i - 1][j - 1]`.

如果`p[j]`为任一字母, 需要判断`p[j]`, `s[i]`是否相等, 如果相等, 则`dp[i][j] = dp[i - 1][j - 1]`; 如果不相等, 则`dp[i][j] = False`.

**p\[k]为\***

由于`*`代表的是匹配0次或任意多次, 因此, 分为两种情况讨论, **只要满足其中的任何一种情况**, 即为`True`.

匹配0次的情况, 即跳过当前的`*`字符, 以及前面紧邻的`.`或字母字符. 则有`dp[i][j] = dp[i][j - 2]`

匹配1\~n次的情况, 需要判断`p[j-1]`与`s[i], s[i-1], ...`的字符是否相等, 一直找到不相等的字符为止, 例如`s[i-a]`与`p[j-1]`不相等, 则`dp[i][j] = dp[i-a][j-2]`.

但其实我们只需要比较`p[j-1]`与`s[i]`是否相等, 因此我们是从左到右搜索, 这样`p[j-1]`与`s[i]`之前的字符是否相等, 已经包含在`dp[i-1][j]`中, 而无需向前继续寻找.

因此我们有, 如果`p[j-1]`与`s[i]`相等, 则`dp[i][j] = dp[i - 1][j]`, 否则为`False`.

因此`p[k]`为`*`的情况下, `dp[i][j] = dp[i][j - 2] or (s[i] == p[j - 1] and dp[i - 1][j])`

状态转移方程考虑完毕.

最后考虑下初始状态. 要考虑空字符串和模式串的情况, 因此如果字符串和匹配串的长度分别为`n`和`m`, 那么我们状态矩阵的大小应为`(n + 1, m + 1)`, 各个维度的索引`0`代表空字符串.

则`dp[0][0] = True`, 空字符串肯定是匹配的. `dp[i][0]`肯定是`False`, 因为任何非空字符串肯定与空模式串不匹配. `dp[0][j]`是要注意的情况, 我们对于非`*`位置肯定是`False`, 而`*`位置, 只能考虑不匹配任何字符的情况, 因此有`dp[0][j] = dp[0][j - 2]`. 这样其实遇到第一个连续的非`*`字符, 至此开始, 后续都是False.

整体代码如下:

```python
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]

        def match(sc, pc):
            return True if pc == '.' else sc == pc

        # 初始化
        dp[0][0] = True
        for j in range(1, m + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2] or (match(s[i - 1], p[j - 2]) and dp[i - 1][j])
                elif match(s[i - 1], p[j - 1]):
                    dp[i][j] = dp[i - 1][j - 1]
        print(dp)
        return dp[-1][-1]
```


---

# 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://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/10-zheng-ze-biao-da-shi-pi-pei.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.