正则表达式匹配

## 1 题目

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

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

**示例 1：**

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

**示例 2:**

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

**示例 3：**

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

**提示：**

* 1 <= s.length <= 20
* 1 <= p.length <= 30
* s 只包含从 a-z 的小写字母。
* p 只包含从 a-z 的小写字母，以及字符 . 和 *。
* 保证每次出现字符 * 时，前面都匹配到有效的字符

## 2 问题分析

1. 本题中**点号通配符其实很好实现**，$s$**中的任何字符**，**只要遇到 $.$ 通配符**，**无脑匹配就完事了**，**主要是这个 $*$ 通配符不好实现**，**一旦遇到 $*$ 通配符**，**前面的那个字符可以选择重复一次**，**可以重复多次**，**也可以一次都不出现**，**针对这个问题**，**我们可以对所有可能出现的情况**，**全部都穷举一遍**，**只要有一种情况可以完成匹配**，**就认为 $p$ 可以匹配 $s$**，**那么一旦涉及两个字符串的穷举**，**我们就应该条件反射地想到动态规划的技巧了**。
2. 我们先脑补一下，**$s$ 和 $p$ 相互匹配的大致过程是两个指针 $i,  j$ 分别在 $s$ 和 $p$ 上移动**，**如果最后两个指针都能移动到字符串的末尾**，**那么就匹配成功**，**反之则匹配失败**。
3. **正则表达算法问题只需要把握住一个基本点**，**看两个字符是否匹配**，**一切逻辑围绕匹配/不匹配两种情况展开即可**：
   1. **如果不考虑 $*$ 通配符**，**面对两个待匹配字符串 $s[i]$ 和 $p[j]$**，**我们唯一能做的就是看他俩是否匹配**：

```java
      bool isMatch(string s, string p) {
          int i = 0, j = 0;
          while (i < s.size() && j < p.size()) {
              // 「.」通配符就是万金油
              if (s.charAt(i) == p.charAt(i) || p.charAt(j) == '.') {
                  // 匹配，接着匹配 s[i+1..] 和 p[j+1..]
                  i++; j++;
              } else {
                  // 不匹配
                  return false;
              }
          }
          return i == j;
      }
      ```
   2. 那么，考虑一下，**如果加入$*$通配符**，**局面就会稍微复杂一些**，不过只要分情况来分析，也不难理解：

1. **当$p[j + 1]$为$*$通配符时**，**我们分情况讨论下**：

1. **如果匹配**，**即$s.charAt(i) = p.charAt(j)$**，**那么有两种情况**：

1. $p.charAt(j)$**匹配多个字符**，比如$s = "aaa", p = "a*"$，**那么$p.charAt(0)$会通过$*$匹配3个字符$a$。**
            2. $p.charAt(j)$**匹配0个字符**，比如$s = "aa", p = a*aa$**，***由于后面的字符可以匹配$s$**，**所以$p.charAt(0)$只能匹配0次**。
         2. **如果不匹配**，**即$s.charAt(i) \ne p.charAt(j)$**，**只有一种情况**：

1. $p.charAt(j)$**只能匹配0次**，**然后看下一个字符是否能和$s.charAt(i)$匹配**，比如说$s = "aa", p = "b*aa"$，**此时$p.charAt(0)$只能匹配0次**。
         3. 综上，我们可以**把之前的代码针对$*$通配符进行一下改造**：

```java
            if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                // 匹配
                if (j < p.size() - 1 && p.charAt(j + 1) == '*') {
                    // 有 * 通配符，可以匹配 0 次或多次
                } else {
                    // 无 * 通配符，老老实实匹配 1 次
                    i++; j++;
                }
            } else {
                // 不匹配
                if (j < p.size() - 1 && p.charAt(j + 1) == '*') {
                    // 有 * 通配符，只能匹配 0 次
                } else {
                    // 无 * 通配符，匹配无法进行下去了
                    return false;
                }
            }
            ```
      2. 整体的思路应该很清晰了，但现在的问题时，**遇到通配符$*$时**，**到底应该是匹配0次还是匹配多次**，**多次是几次**，**这就是一个做【选择】的问题**，**要把所有可能的选择都穷举一遍才能得出结果**，**动态规划的核心就是【状态】和【选择】**，**【状态】无非就是$i$和$j$两个指针的位置**，**【选择】就是$p.charAt(j)$选择匹配几个字符**。
      3. **根据【状态】**，**我们可以定义一个$dp$函数**，**其中$dp(s, i, p, j)$表示$s[i...]$是否可以匹配$p[j...]$**：

```java
         public boolean dp(String s, int i, String p, int j)
         ```
      4. **根据这个定义**，**我们想要的答案就是$i = 0, j = 0$时$dp$函数的结果**，**所以可以这样使用这个$dp$函数**：

```java
         public boolean isMatch(String s, String p) {
             //  指针 i, j 从索引 0 开始移动
             return dp(s, 0, p, 0);
         }
         ```
      5. **可以根据之前的代码写出$dp$函数的主要逻辑**：

```java
         public boolean dp(String s, int i, String p, int j) {
             int m = s.length(), n = p.length();

if (j == n) {return i == m;}
             if (i == m) {
                 //  如果能匹配空串，一定是字符和 * 成对出现
                 if (((n - j) % 2) == 1) {return false;}
                 //  检查是否为 x*y*z* 这种形式
                 for (; j + 1 < n; j += 2) {
                     if (p.charAt(j + 1) != '*') {return false;}
                 }
                 return true;
             }

//  如果备忘录中存在，直接从备忘录中取
             String key = String.format("%s_%s", i, j);
             if (memo.containsKey(key)) {return memo.get(key);}

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                 //  匹配
                 if (j < n - 1 && p.charAt(j + 1) == '*') {
                     //  * 匹配 0 次或多次
                     res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
                 } else {
                     //  * 常规匹配 1 次
                     res = dp(s, i + 1, p, j + 1);
                 }
             } else {
                 //  不匹配
                 if (j < n - 1 && p.charAt(j + 1) == '*') {
                     //  * 匹配 0 次
                     res = dp(s, i, p, j + 2);
                 } else {
                     //  无法继续匹配
                     res = false;
                 }
             }

//  将当前结果计入备忘录
             memo.put(key, res);

return res;
         }
         ```
      6. **根据$dp$函数的定义**，**上面的几种情况都很好解释**：

1. **当前字符可以匹配**：
            1. **通配符匹配0次或多次**：
               1. **将$j$加2**，$i$**不变**，**含义就是直接跳过$p.charAt(j)$和之后的通配符**，**即通配符匹配0次**。

![图片](/media/202202/2022-02-13_1511410.7641277856847676.png)
               2. **将$i$加1**，$j$**不变**，**含义就是$p.charAt(j)$匹配了$s.charAt(i)$**，**但$p.charAt(j)$还可以继续匹配**，**即通配符匹配多次的情况**。

![图片](/media/202202/2022-02-13_1514110.2020226863039436.png)
               3. **上面两种情况只要有一种可以完成匹配即可**，**所以对上面两种情况求或运算**。
            2. **常规匹配1次**：
               1. **由于这个条件分支是无$*$的常规匹配**，**那么如果$s.charAt(i) == p.charAt(j)$**，**就是$i$和$j$分别加1**。

![图片](/media/202202/2022-02-13_1517130.4059230763448286.png)
         2. **当前字符不可以匹配**：
            1. **通配符匹配0次**：
               1. **类似于上面的当前字符可以匹配时通配符匹配0的情况**，**将$j$加2**，**$i$不变**。

![图片](/media/202202/2022-02-13_1523160.06426259020298242.png)
            2. **没有$*$通配符**：
               1. **如果无法匹配**，**也没有$*$通配符**，**那只能说明匹配失败了**。

![图片](/media/202202/2022-02-13_1525000.6853264208756238.png)
      7. 下面我们**考虑一下$dp$函数的$base \; case$**：

1. **一个$base \; case$是$j == p.size()$时**，**按照$dp$函数的定义**，**这意味着模式串$p$已经被匹配完了**，**那么应该看看文本串$s$匹配到哪里了**，**如果$s$也恰好被匹配完**，**则说明匹配成功**：

```
            if (j == p.size) {return i == s.size();}
            ```
         2. 另一个$base \; case$是$i = s.size()$时，按照$dp$函数的定义，这种情况意味着文本串$s$已经全部被匹配完了，此时并不能根据$j$是否等于$p.size()$来判断是否完成匹配，只要$p[j...]$能够匹配空串，就可以算完成匹配，比如说$s = "a", p = "ab*c*"$，当$i$走到$s$末尾的时候，$j$并没有走到$p$的末尾，但是$p$依然可以匹配$s$，代码中使用了一个哈希表$memo$作为备忘录来减少重复遍历问题：

```
            int m = s.length(), n = p.length();

if (j == n) {return i == m;}
            if (i == m) {
                //  如果能匹配空串，一定是字符和 * 成对出现
                if (((n - j) % 2) == 1) {return false;}
                //  检查是否为 x*y*z* 这种形式
                for (; j + 1 < n; j += 2) {
                    if (p.charAt(j + 1) != '*') {return false;}
                }
                return true;
            }

//  如果备忘录中存在，直接从备忘录中取
            String key = String.format("%s_%s", i, j);
            if (memo.containsKey(key)) {return memo.get(key);}

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                //  匹配
                if (j < n - 1 && p.charAt(j + 1) == '*') {
                    //  * 匹配 0 次或多次
                    res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
                } else {
                    //  * 常规匹配 1 次
                    res = dp(s, i + 1, p, j + 1);
                }
            } else {
                //  不匹配
                if (j < n - 1 && p.charAt(j + 1) == '*') {
                    //  * 匹配 0 次
                    res = dp(s, i, p, j + 2);
                } else {
                    //  无法继续匹配
                    res = false;
                }
            }

//  将当前结果计入备忘录
            memo.put(key, res);

return res;
            ```

## 3 参考代码

```java
//  最终结果
boolean res;
//  备忘录
HashMap<String, Boolean> memo = new HashMap<>();

/**
 * 10. 正则表达式匹配
 * @param s 字符串
 * @param p 正则表达式
 * @return  p 是否可以匹配 s
 */
public boolean isMatch(String s, String p) {
    //  指针 i, j 从索引 0 开始移动
    return dp(s, 0, p, 0);
}

/**
 * dp 函数
 * @param s 文本串
 * @param i 文本串索引
 * @param p 模式串
 * @param j 模式串索引
 * @return  p[j:] 是否可以匹配 s[i:]
 */
public boolean dp(String s, int i, String p, int j) {
    int m = s.length(), n = p.length();

if (j == n) {return i == m;}
    if (i == m) {
        //  如果能匹配空串，一定是字符和 * 成对出现
        if (((n - j) % 2) == 1) {return false;}
        //  检查是否为 x*y*z* 这种形式
        for (; j + 1 < n; j += 2) {
            if (p.charAt(j + 1) != '*') {return false;}
        }
        return true;
    }

//  如果备忘录中存在，直接从备忘录中取
    String key = String.format("%s_%s", i, j);
    if (memo.containsKey(key)) {return memo.get(key);}

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
        //  匹配
        if (j < n - 1 && p.charAt(j + 1) == '*') {
            //  * 匹配 0 次或多次
            res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
        } else {
            //  * 常规匹配 1 次
            res = dp(s, i + 1, p, j + 1);
        }
    } else {
        //  不匹配
        if (j < n - 1 && p.charAt(j + 1) == '*') {
            //  * 匹配 0 次
            res = dp(s, i, p, j + 2);
        } else {
            //  无法继续匹配
            res = false;
        }
    }

//  将当前结果计入备忘录
    memo.put(key, res);

return res;
}
```

## 参考文献

1. [10. 正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching)。
2. [东哥手写正则通配符算法，结构清晰，包教包会！](https://mp.weixin.qq.com/s/rnaFK05IcFWvNN1ppNf2ug)