共计 4179 个字符，预计需要花费 11 分钟才能阅读完成。
读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
10. 正则表达式匹配
———–
正则表达式是一个十分强力的工具，本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配」就要求咱们实现一个简略的正则匹配算法，包含「.」通配符和「*」通配符。
这两个通配符是最罕用的，其中点号「.」能够匹配任意一个字符，星号「*」能够让之前的那个字符反复任意次数（包含 0 次）。
比如说模式串 ".a*b" 就能够匹配文本 "zaaab"，也能够匹配 "cb"；模式串 "a..b" 能够匹配文本 "amnb"；而模式串 ".*" 就比拟牛逼了，它能够匹配任何文本。
题目会给咱们输出两个字符串 s 和 p，s 代表文本，p 代表模式串，请你判断模式串 p 是否能够匹配文本 s。咱们能够假如模式串只蕴含小写字母和上述两种通配符且肯定非法，不会呈现 *a 或者 b** 这种不非法的模式串，
函数签名如下：
bool isMatch(string s, string p);对于咱们将要实现的这个正则表达式，难点在那里呢？
点号通配符其实很好实现，s 中的任何字符，只有遇到 . 通配符，无脑匹配就完事了。次要是这个星号通配符不好实现，一旦遇到 * 通配符，后面的那个字符能够抉择反复一次，能够反复屡次，也能够一次都不呈现，这该怎么办？
对于这个问题，答案很简略，对于所有可能呈现的状况，全副穷举一遍，只有有一种状况能够实现匹配，就认为 p 能够匹配 s。那么一旦波及两个字符串的穷举，咱们就应该条件反射地想到动静布局的技巧了。
PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
一、思路剖析
咱们先脑补一下，s 和 p 互相匹配的过程大抵是，两个指针 i, j 别离在 s 和 p 上挪动，如果最初两个指针都能挪动到字符串的开端，那么久匹配胜利，反之则匹配失败。
如果不思考 * 通配符，面对两个待匹配字符 s[i] 和 p[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;
}那么考虑一下，如果退出 * 通配符，场面就会略微简单一些，不过只有分状况来剖析，也不难理解。
当 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[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;
}
}整体的思路曾经很清晰了，但当初的问题是，遇到 * 通配符时，到底应该匹配 0 次还是匹配屡次？屡次是几次？
你看，这就是一个做「抉择」的问题，要把所有可能的抉择都穷举一遍能力得出后果。动静布局算法的外围就是「状态」和「抉择」，「状态」无非就是 i 和 j 两个指针的地位，「抉择」就是 p[j] 抉择匹配几个字符。
二、动静布局解法
依据「状态」，咱们能够定义一个 dp 函数：
bool dp(string& s, int i, string& p, int j);dp 函数的定义如下：
若 dp(s, i, p, j) = true，则示意 s[i..] 能够匹配 p[j..]；若 dp(s, i, p, j) = false，则示意 s[i..] 无奈匹配 p[j..]。
依据这个定义，咱们想要的答案就是 i = 0, j = 0 时 dp 函数的后果，所以能够这样应用这个 dp 函数：
bool isMatch(string s, string p) {
// 指针 i，j 从索引 0 开始挪动
return dp(s, 0, p, 0);能够依据之前的代码写出 dp 函数的次要逻辑：
bool dp(string& s, int i, string& p, int j) {if (s[i] == p[j] || p[j] == '.') {
// 匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 1.1 通配符匹配 0 次或屡次
return dp(s, i, p, j + 2)
|| dp(s, i + 1, p, j);
} else {
// 1.2 惯例匹配 1 次
return dp(s, i + 1, p, j + 1);
}
} else {
// 不匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 2.1 通配符匹配 0 次
return dp(s, i, p, j + 2);
} else {
// 2.2 无奈持续匹配
return false;
}
}
}依据 dp 函数的定义，这几种状况都很好解释：
1.1 通配符匹配 0 次或屡次
将 j 加 2，i 不变，含意就是间接跳过 p[j] 和之后的通配符，即通配符匹配 0 次：
将 i 加 1，j 不变，含意就是 p[j] 匹配了 s[i]，但 p[j] 还能够持续匹配，即通配符匹配屡次的状况：
两种状况只有有一种能够实现匹配即可，所以对下面两种状况求或运算。
1.2 惯例匹配 1 次
因为这个条件分支是无 * 的惯例匹配，那么如果 s[i] == p[j]，就是 i 和 j 别离加一：
2.1 通配符匹配 0 次
相似状况 1.1，将 j 加 2，i 不变：
2.2 如果没有 * 通配符，也无奈匹配，那只能阐明匹配失败了：
看图了解应该很容易了，当初能够思考一下 dp 函数的 base case：
一个 base case 是 j == p.size() 时，依照 dp 函数的定义，这意味着模式串 p 曾经被匹配完了，那么应该看看文本串 s 匹配到哪里了，如果 s 也恰好被匹配完，则阐明匹配胜利：
if (j == p.size()) {return i == s.size();
}另一个 base case 是 i == s.size() 时，依照 dp 函数的定义，这种状况意味着文本串 s 曾经全副被匹配了，那么是不是只有简略地检查一下 p 是否也匹配完就行了呢？
if (i == s.size()) {
// 这样行吗？return j == p.size();}这是不正确的，此时并不能依据 j 是否等于 p.size() 来判断是否实现匹配，只有 p[j..] 可能匹配空串，就能够算实现匹配。比如说 s = "a", p = "ab*c*"，当 i 走到 s 开端的时候，j 并没有走到 p 的开端，然而 p 仍然能够匹配 s。
PS：我认真写了 100 多篇原创，手把手刷 200 道力扣题目，全副公布在 labuladong 的算法小抄，继续更新 。倡议珍藏， 依照我的文章程序刷题，把握各种算法套路后投再入题海就蛟龙得水了。
所以咱们能够写出如下代码：
int m = s.size(), n = p.size();
if (i == s.size()) {
// 如果能匹配空串，肯定是字符和 * 成对儿呈现
if ((n - j) % 2 == 1) {return false;}
// 查看是否为 x*y*z* 这种模式
for (; j + 1 < p.size(); j += 2) {if (p[j + 1] != '*') {return false;}
}
return true;
}依据以上思路，就能够写出残缺的代码：
/* 计算 p[j..] 是否匹配 s[i..] */
bool dp(string& s, int i, string& p, int j) {int m = s.size(), n = p.size();
// base case
if (j == n) {return i == m;}
if (i == m) {if ((n - j) % 2 == 1) {return false;}
for (; j + 1 < n; j += 2) {if (p[j + 1] != '*') {return false;}
}
return true;
}
// 记录状态 (i, j)，打消重叠子问题
string key = to_string(i) + "," + to_string(j);
if (memo.count(key)) return memo[key];
bool res = false;
if (s[i] == p[j] || p[j] == '.') {if (j < n - 1 && p[j + 1] == '*') {res = dp(s, i, p, j + 2)
|| dp(s, i + 1, p, j);
} else {res = dp(s, i + 1, p, j + 1);
}
} else {if (j < n - 1 && p[j + 1] == '*') {res = dp(s, i, p, j + 2);
} else {res = false;}
}
// 将以后后果记入备忘录
memo[key] = res;
return res;
}代码中用了一个哈希表 memo 打消重叠子问题，因为正则表白算法的递归框架如下：
bool dp(string& s, int i, string& p, int j) {dp(s, i, p, j + 2); // 1
dp(s, i + 1, p, j); // 2
dp(s, i + 1, p, j + 1); // 3
}那么，如果让你从 dp(s, i, p, j) 失去 dp(s, i+2, p, j+2)，至多有两条门路：1 -> 2 -> 2 和 3 -> 3，那么就阐明 (i+2, j+2) 这个状态存在反复，这就阐明存在重叠子问题。
动静布局的工夫复杂度为「状态的总数」*「每次递归破费的工夫」，本题中状态的总数当然就是 i 和 j 的组合，也就是 M * N（M 为 s 的长度，N 为 p 的长度）；递归函数 dp 中没有循环（base case 中的不思考，因为 base case 的触发次数无限），所以一次递归破费的工夫为常数。二者相乘，总的工夫复杂度为 O(MN)。
空间复杂度很简略，就是备忘录 memo 的大小，即 O(MN)。
_____________
点击 我的主页 看更多优质文章。
