字符串匹配（动态规划）

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;
}