题⽬描述

请实现⼀个函数⽤来匹配包括’ . ‘和’ * ‘的正则表达式。模式中的字符’ . ‘表示任意⼀个字符， ⽽’ * ‘表示它前⾯的字符可以出现任意次（包含0 次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串" aaa “与模式” a.a “和” abaca “匹配，但是与” aa.a “和” ab*a “均不匹 配

示例1 输⼊: “aaa”,“a*a” 返回值: true

示例2 输⼊：“aad”,“cad” 返回值：true 说明：因为这⾥ c 为 0 个，a被重复⼀次， * 表示零个或多个a。因此可以匹配字符串 “aad”。

示例3 输⼊：”","." 返回值：true 说明："." 表示可匹配零个或多个（’*’）任意字符（’.’）

思路及解答

递归

分类讨论，原串定义为str ,模式串为pattern 。`

  • 如果pattern ⻓度为0

    • 且str ⻓度为0 ,说明刚刚好匹配完，返回ture

    • str ⻓度不为0，说明没有匹配完，返回false

  • 如果pattern 的⻓度⼤于0

    • 如果pattern 的⻓度⼤于1，且第2 个字符是*，说明前⾯的字符可以匹配0， 1 或者多次

      • 分为两种情况讨论：⼀种是直接把* 和* 前⾯的字符去掉，相当于匹配了0 个，然后接着⽐较；另外⼀种是，如果str 的⻓度⼤于0，并且第⼀个字符匹配，那就把str 的第⼀个字符去掉，两者接着匹配。

    • 否则，说明第⼆个字符不是 *，那么就直接⽐较第⼀个字符是不是匹配，同时将后⾯的字符进⾏匹配。

注意：上⾯说的第⼀个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为’ . ‘的情况。

  • 时间复杂度：最坏O((m+n)2^(m+n))

  • 空间复杂度：O(m²+n²)递归栈

记忆化搜索（递归+缓存）

在递归基础上添加缓存，避免重复计算。使用二维数组存储s[i:]和p[j:]的匹配结果，避免重复递归

  • 时间复杂度：O(m×n)

  • 空间复杂度：O(m×n)

动态规划（推荐）

动态规划：

  1. ⾸先定义状态：⽤⼀个⼆维数组（套路） dp[i][j] ⽤来表示str 的前i 个字符和pattern 的前j 个字符是否匹配。

  2. 初始化简单状态

  • dp[0][0]= true ,表示两个空的字符串是匹配的。

  • dp 数组的⾸列，除了dp[0][0] 为true，其他的dp[i][0]都是false 。因为pattern 为空，但是s 不为空的时候，肯定不匹配。

  • dp 的⾸⾏dp[0][j]，也就是str 为空的时候，如果pattern 的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0 次。

  1. 初始化前⾯之后，后⾯的从索引1 开始匹配：

  2. pattern 的第j 个字符为“ * ”(即是 pattern[j-1]=='*' )

1. 如果`dp[i][j-2]==true`，那么`dp[i][j]=true` (相当于str的前i和pattern的前j-2个字符匹配，此时的* 前⾯的那个字符出现了0 次)。

1. 如果`dp[i-1][j]==true` 且`str[i-1]==pattern[j-2]`，则`dp[i][j] =true` 。（如果str 的前i - 1 个字符和pattern 的前j 个字符匹配，并且str 的第i 个字符和pattern 的第j - 1 个字符相等,相当于‘ * ’前⾯的字符出现了1 次）

1. 如果`dp[i-1][j]=true` 且`pattern[j-2]=='.'` 的时候，则`dp[i][j]=true` 。(表示str 的前i-1 个和patten 的前j 个匹配，并且pattern 的第j-1 个是‘ . ’，第j 个是‘ * ’,那么说明可以匹配任何字符任何次数，⾃然str 可以多匹配⼀个字符。)
  1. pattern 的第j 个字符不为“ * ”(即是pattern[j-1]！='*' )
1. 如果`dp[i - 1][j - 1]=true and str[i - 1] == pattern[j - 1]` 时，则`dp[i][j]=true` 。（也就是前⾯匹配，接下来的字符⼀样匹配）

1. 如果`dp[i - 1][j - 1]=true` 且`pattern[i-1]=='.'`，那么`dp[i][j]=true` 。(其实也是. 可以匹配任何字符)

处理完数组之后，最后返回dp[n-1][m-1]，也就是str 的前n 个和pattern 的前m 个字符是否匹配。

  • 时间复杂度 O(mn) ： 其中 m , n 分别为 str 和 pattern 的⻓度，状态转移需遍历整个 dp 矩阵。

  • 空间复杂度 O(mn) ： 状态矩阵 dp 使⽤ O(mn) 的额外空间。

状态机优化（空间优化DP）

状态机优化：滚动数组降低空间复杂度，只保留当前行和上一行的状态，空间优化到O(n)

  • 时间复杂度：O(m×n)

  • 空间复杂度：O(n)