1.通配符匹配（44 - 难）
题目描述：给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
- '?' 可以匹配任何单个字符。
- '*' 可以匹配任意字符串（包括空字符串）。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *
示例 :
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
思路：本题是典型的字符串匹配的题目。动态规划：
-
dp[i][j]：p的前i个字符与s的前j个字符是否匹配 - 状态转移方程：根据匹配规则，分为两种情况
- 两个字符串对应位置相同或者p串对应位置为“?”
- p串对应位置为“*”，此时星号可以匹配字母或者是空字符
注意：当p为空且s不为空，一定不能匹配；反之不一定，如果p串全部为星号，则能匹配（全部匹配空）。
代码实现：
public boolean isMatch(String s, String p) {
int len1 = p.length();
int len2 = s.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 1; i < len1 + 1; i++) {
if (p.charAt(i - 1) != '*') {
break;
}
dp[i][0] = true;
}
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(i - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[len1][len2];
}
2.正则表达式匹配（10 - 难）
题目描述：给你一个字符串 s 和一个字符规律 p（都可为空），请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
注意：题目保证每次出现星号，前面都能匹配到有效字符！
示例 :
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
思路：本题与上一题类似，但是本题难点在于讨论星号的情况：
- 匹配不上，可以将字符+*全部忽略，即匹配0个
- 如果能够匹配上，匹配0个，或者匹配掉s串的当前字符。
注意：当s为空且p不为空，需要检查p的结构；反之一定不能匹配。
代码实现：
public boolean isMatch(String s, String p) {
int len1 = p.length();
int len2 = s.length();
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
// 对于匹配串s为空且p不为空，判断模式串是否为【字符+*】结构
for (int i = 1; i < len1 + 1; i++) {
if (p.charAt(i - 1) == '*') {
dp[i][0] = dp[i - 2][0];
}
}
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
if (p.charAt(i - 1) == '*') {
if (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.') {
dp[i][j] = dp[i - 2][j] || dp[i][j - 1];
} else {
dp[i][j] = dp[i - 2][j];
}
} else {
if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[len1][len2];
}
3.编辑距离（72 - 难）
题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 :
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
思路：本题word1可以看成模式串，即字符串匹配问题。
-
dp[i][j]：word1前i个字符转换成word2前j个字符的最少操作数 - 状态转移方程：关键是讨论三种操作状态，取最小值+1，做为当前的最小操作数
- 插入操作：
dp[i][j - 1]，即等于word1前i个字符转换成word2前j - 1个字符的最少操作数 -
删除操作（即不用word1第i个元素）：
dp[i - 1][j]，即等于word1前i - 1个字符转换成word2前j个字符的最少操作数 - 替换操作：
dp[i - 1][j - 1]
- 插入操作：
- 初始化：
- word1为空且word2不为空，最小转化次数为word1.length()，即全部添加；
- 否则，最小转化次数为word2.length()，即全部删除。
代码实现：
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i < len1 + 1; i++) {
dp[i][0] = i;
}
for (int j = 1; j < len2 + 1; j++) {
dp[0][j] = j;
}
for (int i = 1; i < len1 + 1; i++) {
for (int j = 1; j < len2 + 1; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
}
return dp[len1][len2];
}
4.最长公共子序列（1143 - 中）
题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 :
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
思路：本题与上题类似，使用动态规划解决比较好，因为本题没有规定谁是谁的子串。
关键是：当两个字符不同是，我们需要取 i 字符或 j 字符不取的最大值。具体见代码。
代码实现：
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
5.两个字符串的删除操作（583 - 中）
题目描述：给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例 :
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
思路：将问题转化一下，本题本质：求两个字符串的最长子序列，与上题相同，最后直接返回多余的长度，即使两个字符串相同的最小操作次数。
ps：先将字符串转化为字符数组的方式比直接使用charAt()效率高。
代码实现：
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
char[] str1 = word1.toCharArray();
char[] str2 = word2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - 2 * dp[m][n];
}
6.不相交的线（1035 - 中）
题目描述：在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
- nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 :
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
思路：本题本质：找两个数组的最长重复子序列，最长子序列的长度就是可以绘制的最大连接数。
ps：对于自定义的数据类型++i的效率高于i++。但是有的编译器进行了优化。
- 原因：i++需要先取出i值，再进行+1，所以用到temp存放当前值。i++必须要有一个临时对象才可以完成
代码实现：
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int n1 = nums1.length, n2 = nums2.length;
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i < n1 + 1; ++i) {
for (int j = 1; j < n2 + 1; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
7.最长重复子数组（718 - 中）
题目描述：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 :
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
思路：dp数组定义与上述公共子序列基本相同。
dp[i][j]表示第一个数组 A 前 i 个元素和数组 B 前 j 个元素组成的最长公共子数组(相当于子串)的长度。与公共子序列不同的是，当两个数组元素对比不同时，因为子数组是连续的，所以
dp[i][j] == 0。
注意：由于状态方程不同，当不相同时清零，所以我们要更新最大值。
代码实现：
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int max = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
max = Math.max(max, dp[i][j]);
}
}
return max;
}
