经典动态规划：正则表达式

正则表达式是一个非常强力的工具，本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配」就要求我们实现一个简单的正则匹配算法，包括「.」通配符和「*」通配符。

这两个通配符是最常用的，其中点号「.」可以匹配任意一个字符，星号「*」可以让之前的那个字符重复任意次数（包括 0 次）。

比如说模式串 ".a*b" 就可以匹配文本 "zaaab"，也可以匹配 "cb"；模式串 "a..b" 可以匹配文本 "amnb"；而模式串 ".*" 就比较牛逼了，它可以匹配任何文本。

题目会给我们输入两个字符串 s 和 p，s 代表文本，p 代表模式串，请你判断模式串 p 是否可以匹配文本 s。我们可以假设模式串只包含小写字母和上述两种通配符且一定合法，不会出现 *a 或者 b** 这种不合法的模式串，

函数签名如下：

boolean isMatch(string s, string p);

bool isMatch(string s, string p);

def isMatch(s: str, p: str) -> bool:

func isMatch(s string, p string) bool

var isMatch = function(s, p) {}

对于我们将要实现的这个正则表达式，难点在那里呢？

点号通配符其实很好实现，s 中的任何字符，只要遇到 . 通配符，无脑匹配就完事了。主要是这个星号通配符不好实现，一旦遇到 * 通配符，前面的那个字符可以选择重复一次，可以重复多次，也可以一次都不出现，这该怎么办？

对于这个问题，答案很简单，对于所有可能出现的情况，全部穷举一遍，只要有一种情况可以完成匹配，就认为 p 可以匹配 s。那么一旦涉及两个字符串的穷举，我们就应该条件反射地想到动态规划的技巧了。

一、思路分析

我们先脑补一下，s 和 p 相互匹配的过程大致是，两个指针 i, j 分别在 s 和 p 上移动，如果最后两个指针都能移动到字符串的末尾，那么久匹配成功，反之则匹配失败。

如果不考虑 * 通配符，面对两个待匹配字符 s[i] 和 p[j]，我们唯一能做的就是看他俩是否匹配：

boolean isMatch(String s, String p) {
    int i = 0, j = 0;
    while (i < s.length() && j < p.length()) {
        // 「.」通配符就是万金油
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            // 匹配，接着匹配 s[i+1..] 和 p[j+1..]
            i++; j++;
        } else {
            // 不匹配
            return false;
        }
    }
    return i == j;
}

bool isMatch(string s, string p) {
    int i = 0, j = 0;
    while (i < s.size() && j < p.size()) {
        // 「.」通配符就是万金油
        if (s[i] == p[j] || p[j] == '.') {
            // 匹配，接着匹配 s[i+1..] 和 p[j+1..]
            i++; j++;
        } else {
            // 不匹配
            return false;
        }
    }
    return i == j;
}

def isMatch(s: str, p: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(p):
        # 「.」通配符就是万金油
        if s[i] == p[j] or p[j] == '.':
            # 匹配，接着匹配 s[i+1..] 和 p[j+1..]
            i += 1
            j += 1
        else:
            # 不匹配
            return False
    return i == j

func isMatch(s string, p string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(p) {
        // 「.」通配符就是万金油
        if s[i] == p[j] || p[j] == '.' {
            // 匹配，接着匹配 s[i+1..] 和 p[j+1..]
            i++
            j++
        } else {
            // 不匹配
            return false
        }
    }
    return i == j
}

var isMatch = function(s, p) {
    let i = 0, j = 0;
    while (i < s.length && j < p.length) {
        // 「.」通配符就是万金油
        if (s[i] === p[j] || p[j] === '.') {
            // 匹配，接着匹配 s[i+1..] 和 p[j+1..]
            i++; j++;
        } else {
            // 不匹配
            return false;
        }
    }
    return i === j;
};

那么考虑一下，如果加入 * 通配符，局面就会稍微复杂一些，不过只要分情况来分析，也不难理解。

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

1、如果 s[i] == p[j]，那么有两种情况：

1.1 p[j] 有可能会匹配多个字符，比如 s = "aaa", p = "a*"，那么 p[0] 会通过 * 匹配 3 个字符 "a"。

1.2 p[i] 也有可能匹配 0 个字符，比如 s = "aa", p = "a*aa"，由于后面的字符可以匹配 s，所以 p[0] 只能匹配 0 次。

2、如果 s[i] != p[j]，只有一种情况：

p[j] 只能匹配 0 次，然后看下一个字符是否能和 s[i] 匹配。比如说 s = "aa", p = "b*aa"，此时 p[0] 只能匹配 0 次。

综上，可以把之前的代码针对 * 通配符进行一下改造：

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
    // 匹配
    if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符，老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 通配符，匹配无法进行下去了
        return false;
    }
}

if (s[i] == p[j] || p[j] == '.') {
    // 匹配
    if (j < p.size()-1 && p[j+1] == '*') {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符，老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if (j < p.size()-1 && p[j+1] == '*') {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 通配符，匹配无法进行下去了
        return false;
    }
}

if s[i] == p[j] or p[j] == '.':
    # 匹配
    if j < len(p) - 1 and p[j + 1] == '*':
        # 有 * 通配符，可以匹配 0 次或多次
        pass
    else:
        # 无 * 通配符，老老实实匹配 1 次
        i += 1
        j += 1
else:
    # 不匹配
    if j < len(p) - 1 and p[j + 1] == '*':
        # 有 * 通配符，只能匹配 0 次
        pass
    else:
        # 无 * 通配符，匹配无法进行下去了
        return False

if s[i] == p[j] || p[j] == '.' {
    // 匹配
    if j < len(p) - 1 && p[j + 1] == '*' {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符，老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if j < len(p) - 1 && p[j + 1] == '*' {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 通配符，匹配无法进行下去了
        return false
    }
}

var exampleFunc = function(s, p) {
  if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
      // 匹配
      if (j < p.length - 1 && p.charAt(j + 1) == '*') {
          // 有 * 通配符，可以匹配 0 次或多次
      } else {
          // 无 * 通配符，老老实实匹配 1 次
          i++; j++;
      }
  } else {
      // 不匹配
      if (j < p.length - 1 && p.charAt(j + 1) == '*') {
          // 有 * 通配符，只能匹配 0 次
      } else {
          // 无 * 通配符，匹配无法进行下去了
          return false;
      }
  }
}

整体的思路已经很清晰了，但现在的问题是，遇到 * 通配符时，到底应该匹配 0 次还是匹配多次？多次是几次？

你看，这就是一个做「选择」的问题，要把所有可能的选择都穷举一遍才能得出结果。动态规划算法的核心就是「状态」和「选择」，「状态」无非就是 i 和 j 两个指针的位置，「选择」就是 p[j] 选择匹配几个字符。

二、动态规划解法

根据「状态」，我们可以定义一个 dp 函数：

boolean dp(String s, int i, String p, int j);