Appearance
第10讲：高频真题解析III（上)
这节课将分析三道比较难的题目，希望能帮助大家拓宽解题的思路。主要内容包括：
正则表达式匹配
柱状图中的最大矩形
实现 strStr() 函数
例题分析一
LeetCode 第 10 题，正则表达式匹配：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
注意：所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。
说明：
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
解释：'p'与'i'无法匹配。
解题思路
不要害怕，这道题只要求实现正则表达式里的两个小功能。
判断 s 和 p 匹配
举例：给定两个字符串 s 和 p，判断 s 和 p 是否匹配。
解法：s 和 p 必须要相等。定义两个指针 i 和 j，分别指向 s 和 p 的第一个字符，然后逐个去比较，一旦发现不相等，就立即知道 s 和 p 不匹配。
此时，假设 s 字符串的长度为 m，p 字符串的长度为 n，s 和 p 匹配的条件就是 s 和 p 从头到尾一直匹配，即 i == m 同时 j == n 是 s 和 p 匹配的唯一条件。
点匹配符 '.'
'.' 匹配任意单个字符，首先要明确的是，它是一一对应关系，和 '*' 匹配符不一样。举例说明如下。
输入:
s = "leetcode"
p = "l..tc..e"
输出: true
因为 '.' 可以匹配任何字符，即，一旦遇上了 '.' 匹配符，可以让 i 指针和 j 指针同时跳到下一个位置。
星匹配符 '*'
'*' 匹配符较难，先要理解这个星匹配符的定义。题目" '*' 匹配零个或多个前面的那一个元素"中包含三个重要的信息：
它匹配的是 p 字符串中，该 '*' 前面的那个字符。
它可以匹配零个或多个。
'*' 匹配符前面必须有一个非星的字符。
因此，在分析 '*' 匹配符的时候，一定要把 '*' 以及它前面的一个字符看作为一个整体， '*' 不能单独作为一个个体来看（例如点匹配符）。例如，p 字符串是 a *，则把 (a*) 当作一个整体来看。
对 p 字符串说明如下。
p 可以表示空字符串，因为 '*' 可以匹配 0 个前面的字符，即当有 0 个 a 的时候，为空字符串。
a* 还能匹配一个 a，两个 a，三个 a，一直到无穷个 a。
当 p 等于 '.*' 的时候，可以表示一个空字符串，也可以表示一个点，两个点，三个点，一直到无穷个点。即它可以表示任何长度的一段字符串，包括空串。
举例说明
输入：
s = "aaabcd"
p = "ac*a*b.."
- 用两个指针 i 和 j 分别指向 s 和 p 的开头。
- 在 p 字符串里，a 的下一个字符是 c，不是 '*'，比较 s[i] 和 p[j]。因为它们都是字符 a，所以这个位置匹配正确，i 和 j 同时指向下一个。此时 j 的下一个字符是 '*'，要将 c* 当作一个整体去看待。
- 将 c* 看成是空字符，p 如下所示。
- 若匹配中不一致即 c* 不能当作空字符串，则当作一个 c 字符，此时 p 如下。
- 若不行，则看作两个 c。
以此类推，应用了回溯的思想。
对于将 c* 作为空字符串的情况。每一次，都要看看当前 j 指向的字符的下一个是不是 '*'。如果是 '*'，就要作为整体考虑。很明显，a 的下一个字符是 '*'。
同样，先将 a* 作为空字符串看待。此时，a != b，两个字符串不匹配，因此回溯.现在将 a* 看成是一个 a，此时 a = a，两个位置的字符匹配。
j 的下一个字符不是 '*'，而是点号，比较 s[i] 和 p[j]，发现 a != b。于是再次回溯，将 a* 看成是两个 a，回到刚才的位置。
最后遇到了两个点号，由于点号可以匹配任何字符，因此可以直接忽略。i 和 j 同时往前一步，再次遇到了点号。i 和 j 继续往前一步。
此时，i 和 j 都已经同时结束了各自的遍历，表明 s 和 p 是匹配的。
提示：重点是把这种回溯的思想掌握好。对于这道题，可以采用递归的写法，也可以采用动态规划的写法。
递归法一
一开始，用两个指针 i 和 j 分别指向字符串 s 和 p 的第一个字符，当我们发现它们指向的字符相同时，我们同时往前一步移动指针 i 和 j。
接下来重复进行相同的操作，即，若将函数定义为 isMatch(String s, int i, String p, int j) 的话，通过传递 i 和 j，就能实现重复利用匹配逻辑的效果。
当遇到点匹配符的时候，方法类似。
来看看当遇到星匹配符的情况，举例说明如下。要不断地用 a* 去表示一个空字符串，一个 a，两个 a，一直到多个 a......
当 a* 表示空字符串的时候，i 和 j 应该如何调整呢？此时 i 保持不变，j+2，递归调用函数的时候，变成 isMatch(s, i, p, j + 2)。
此时，指向的字符和 j 指向的字符不匹配，于是回溯，回到原来的位置。11:57
用 a* 去表示一个 a，i 指向的字符与 a 匹配，那么 i+1。指针 j，已经完成了用 a* 去表示一个 a 的任务，接下来要指向 b，调用的时候应该是 isMatch(s, i + 1, p, j + 2)。
i 指向的字符和 j 指向的字符不匹配，又进行回溯，但是不用回到最开始的位置。已知用 a* 去表示空字符串不行，表示一个 a 也不行，那么尝试两个 a 字符，于是，i 再往前一步，用 a* 去匹配两个 a，i 就到了 b 的位置上，调用的时候就是 isMatch(s, i + 2, p, j + 2)。
不断地这样操作，一旦遇到了 '*' 组合，就不断地尝试，直到最后满足匹配；或者尝试过所有的可能还是不行则表示 s 和 p 无法匹配。
代码实现
根据上面的思路，一起来写递归的实现。主体函数如下。
boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
return isMatch(s, 0, p, 0);
}主体函数非常简单，一开始做简单的判断，只要 s 和 p 有一个为 null，就表示不匹配。
注意：面试的时候，一定要注意对这些基本情况的考量，千万不要认为输入的值都是有效的。
接下来实现递归函数。
boolean isMatch(String s, int i, String p, int j) {
int m = s.length();
int n = p.length();
// 看看pattern和字符串是否都扫描完毕
if (j == n) {
return i == m;
}
// next char is not '*': 必须满足当前字符并递归到下一层
if (j == n - 1 || p.charAt(j + 1) != '*') {
return (i < m) &&
(p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)) &&
isMatch(s, i + 1, p, j + 1);
}
// next char is '*', 如果有连续的s[i]出现并且都等于p[j]，一直尝试下去
if (j < n - 1 && p.charAt(j + 1) == '*') {
while ((i < m) && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))) {
if (isMatch(s, i, p, j + 2)) {
return true;
}
i++;
}
}
// 接着继续下去
return isMatch(s, i, p, j + 2);
}函数接受四个输入参数，s 字符串，p 字符串，i 指针，j 指针。
开始时计算 s 字符串和 p 字符串的长度，分别记为 m 和 n。
当 j 指针遍历完了 p 字符串后，可以跳出递归，而 i 也刚好遍历完，说明 s 和 p 完全匹配。
判断 j 字符的下一个是不是 '*'，不是，则递归地调用 isMatch 函数，i + 1，j + 1。
若是，则不断地将它和 '*' 作为一个整体，分别去表示空字符串，一个字符，两个字符，依此类推。如果其中一种情况能出现 s 和 p 的匹配，就返回 true。
while 循环是整个递归算法的核心，前提条件如下。
i 指向的字符必须要能和 j 指向的字符匹配，其中 j 指向的可能是点匹配符。
若无法匹配，i++，即用 '*' 组合去匹配更长的一段字符串。
当 i 字符和 j 字符不相同，或者 i 已经遍历完了 s 字符串，同时 j 字符后面跟着一个 '*'的情况，只能用 '*'组合去表示一个空字符串，然后递归下去。
递归法二
上法是从前往后进行递归地调用，现在从后往前地分析这个问题。例如：
s = "aaabcd"
p = "a*b.d"实现过程如下所示。
p 字符串的最后一个字符 d 必须要和 s 字符串的最后一个字符相同，才能使 p 有可能与 s 匹配，那么当它们都相同的时候，问题规模也缩小。
p 字符串的最后一个字符不是 '*'，而是点号。它可以匹配 s 字符串里的任意一个字符，且它是最后一个，所以对应的就是 s 字符串里的 c，很明显互相匹配，继续缩小问题规模。
同样，b 不是 '*'，比较它与 s 字符串的最后一个字符是否相同，是，则继续缩小问题规模。
遇到 '*'，'*'可以表示一个空字符串，与前一个字符表示空字符串的时候，将问题变成了判断两个字符串是否匹配，其中，s 等于 aaa，而 p 是空字符串，很明显不能匹配。
用 a* 去表示一个 a。
p 的最后一个还是 '*'，用同样的策略。
继续用 a* 去表示一个 a。
用 a* 去表示空字符串。
最后 s 和 p 都变成了空字符串，互相匹配。
代码实现
主函数代码如下。
boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
return isMatch(s, s.length(), p, p.length());
}在主函数里，进行一些简单基础的判断，如果 s 和 p 有一个是 null，则返回 false。
递归函数代码如下。
boolean isMatch(String s, int i, String p, int j) {
if (j == 0) return i == 0;
if (i == 0) {
return j > 1 && p.charAt(j - 1) == '*' && isMatch(s, i, p, j - 2);
}
if (p.charAt(j - 1) != '*') {
return isMatch(s.charAt(i - 1), p.charAt(j - 1)) &&
isMatch(s, i - 1, p, j - 1);
}
return isMatch(s, i, p, j - 2) || isMatch(s, i - 1, p, j) &&
isMatch(s.charAt(i - 1), p.charAt(j - 2));
}
boolean isMatch(char a, char b) {
return a == b || b == '.';
}递归函数的输入参数有四个，分别是字符串 s，当前字符串 s 的下标，字符串 p，以及字符串 p 的当前下标。由主函数可以看到，两个字符串的下标都是从最后一位开始。
若 p 字符串为空，并且如果 s 字符串也为空，就表示匹配。
当 p 字符串不为空，而 s 字符串为空，如上例所示，当 s 为空字符串，而 p 等于 a*，此时只要 p 总是由 '*'组合构成，一定能满足匹配，否则不行。
若 p 的当前字符不是 '*'，判断当前的两个字符是否相等，如果相等，就递归地看前面的字符。
否则，如果 p 的当前字符是 '*'：
用 '*' 组合表示空字符串，看看是否能匹配；
用 '*' 组合表示一个字符，看看能否匹配。
动态规划法
递归的方法比较好理解，但是容易造成重叠计算。为了避免重叠计算，可以用动态规划，自底向上地实现刚才的策略。
代码实现
// 分别用 m 和 n 表示 s 字符串和 p 字符串的长度
boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
// 定义一个二维布尔矩阵 dp
boolean[][] dp = new boolean[m + 1][n + 1];
// 当两个字符串的长度都为 0，也就是空字符串的时候，它们互相匹配
dp[0][0] = true;
for (int j = 1; j <= n; j++) {
dp[0][j] = j > 1 && p.charAt(j - 1) == '*' && dp[0][j - 2];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// p 的当前字符不是 '*'，判断当前的两个字符是否相等，如果相等，就看 dp[i-1][j-1] 的值，因为它保存了前一个匹配的结果
if (p.charAt(j - 1) != '*') {
dp[i][j] = dp[i - 1][j - 1] &&
isMatch(s.charAt(i - 1), p.charAt(j - 1));
} else {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j] &&
isMatch(s.charAt(i - 1), p.charAt(j - 2));
}
}
}
return dp[m][n];
}
boolean isMatch(char a, char b) {
return a == b || b == '.';
}注意：
初始化二维矩阵第一行的所有值时，当 s 字符串为空，对于 p 字符串的任何一个位置，要使到这个位置的子串能和空字符串匹配，要求该子串都是由一系列的 '*' 组合构成。
对二维矩阵填表，运用到的逻辑跟递归一摸一样。
p 的当前字符不是 '*'，判断当前的两个字符是否相等。如果相等，就看 dp[i-1][j-1] 的值，因为它保存了前一个匹配的结果。
如果 p 的当前字符是 '*'：
用 '*' 组合表示空字符串，能否匹配，也就是 dp[i][j - 2]；
用 '*' 组合表示一个字符，能否匹配，也就是 dp[i - 1][j]。
复杂度分析
运用动态规划，把时间复杂度控制在 O(n^2^)，而空间复杂度也是 O(n^2^)。
建议：LeetCode 上有一道跟这题十分类似的题目，第 44 题，通配符匹配。分析例题的思路，所运用的策略，以及代码的实现，都有很多非常相似的地方。大家一定要去做做看，举一反三才能加深印象。