> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/niu-ke-0122-kun-nan-zheng-ze-biao-da-shi-pi-pei.md).

# 正则表达式匹配

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/problems/2022/05/pages/R5NyOzkn3qAZy7wCx1pS#动态规划)

> [正则表达式匹配\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4)

**问题简述**

```
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
```

**思路：动态规划**

* 定义 `dp(i, j)` 表示 `s[:i]` 与 `t[:j]` 是否匹配；
* 难点是要把所有情况考虑全面，主要是初始化，和 `p[j - 1] == '*'` 的情况；

<details>

<summary><strong>Python 递归写法</strong></summary>

```python
class Solution:
    def match(self , s: str, t: str) -> bool:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 and j == 0: return True
            if j == 0: return False
            if i == 0: # s='', t='a*b*' 的情况
                return j > 1 and t[j - 1] == '*' and dp(0, j - 2)
            
            # s='abc', t='abc' 或 'ab.'
            r1 = (s[i - 1] == t[j - 1] or t[j - 1] == '.') and dp(i - 1, j - 1)
            # s='abc', t='abcd*' 的情况，* 匹配了 0 个字符，所以下一步需要跳过 *，即 dp(i, j-2)
            r2 = j > 1 and t[j - 1] == '*' and dp(i, j - 2)
            # s='abc', t='abc*' 或 'ab.*' 的情况，* 匹配了至少 1 和字符，下一步需要继续尝试匹配 *，所以是 dp(i-1, j)
            r3 = j > 1 and t[j - 1] == '*' and (s[i - 1] == t[j - 2] or t[j - 2] == '.') and dp(i - 1, j)
            
            return r1 or r2 or r3
        
        # 本题保证了提供的 t 是合法的，所以其实可以去掉 j>1 的判断
        return dp(len(s), len(t))
```

</details>

<details>

<summary><strong>Python 迭代写法</strong></summary>

```python
class Solution:
    def match(self , s: str, t: str) -> bool:
        
        m, n = len(s), len(t)
        # dp[i][j] 表示的是 s[:i] 和 t[:j] 是否匹配，所以需要初始化为 m+1 和 n+1
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):  # 遍历范围是 0 ~ m+1
            for j in range(n + 1):  # 遍历范围是 0 ~ n+1
                if i == 0 and j == 0: dp[i][j] = True
                elif j == 0: dp[i][j] = False
                elif i == 0: # s='', t='a*b*' 的情况
                    dp[i][j] =  j > 1 and t[j - 1] == '*' and dp[0][j - 2]
                else:
                    # s='abc', t='abc' 或 'ab.'
                    r1 = (s[i - 1] == t[j - 1] or t[j - 1] == '.') and dp[i - 1][j - 1]
                    # s='abc', t='abcd*' 的情况，* 匹配了 0 个字符，所以下一步需要跳过 *，即 dp(i, j-2)
                    r2 = j > 1 and t[j - 1] == '*' and dp[i][j - 2]
                    # s='abc', t='abc*' 或 'ab.*' 的情况，* 匹配了至少 1 和字符，下一步需要继续尝试匹配 *，所以是 dp(i-1, j)
                    r3 = j > 1 and t[j - 1] == '*' and (s[i - 1] == t[j - 2] or t[j - 2] == '.') and dp[i - 1][j]

                    dp[i][j] = r1 or r2 or r3
        
        # 本题保证了提供的 t 是合法的，所以其实可以去掉 j>1 的判断
        return dp[-1][-1]
```

</details>