最长公共子序列（LCS）

题目	难度
双串问题：最经典双串 LCS 系列
1143. 最长公共子序列	中等
712. 两个字符串的最小 ASCII 删除和	中等
718. 最长重复子数组	中等
583. 两个字符串的删除操作	中等	同 1143
1035. 不相交的线	中等	同 1143
1092. 最短公共超序列	困难	同 1143
双串问题：字符串匹配系列
72. 编辑距离	困难
DD-2019002. 英文单词拼写纠错推荐	简单	同 72
44. 通配符匹配	困难
10. 正则表达式匹配	困难
双串问题：其它双串 dp[i][j] 问题
97. 交错字符串	中等
115. 不同的子序列	困难
双串问题：带维度双串 dp[i][j][k]
87. 扰乱字符串	困难

1143. 最长公共子序列

public class Solution1143 {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();

        // f[i][j] 表示 text1 前 i 个元素与 text2 前 j 个元素的最长公共子序列
        int[][] f = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[n][m];
    }
}

712. 两个字符串的最小 ASCII 删除和

public class Solution712 {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        // f[i][j] 表示 s1 前 i 个元素与 s2 前 j 个元素的最小ASCII删除和
        int[][] f = new int[n + 1][m + 1];

        // 初始状态
        for (int i = 1; i <= n; i++) {
            f[i][0] = f[i - 1][0] + s1.codePointAt(i - 1);
        }
        for (int j = 1; j <= m; j++) {
            f[0][j] = f[0][j - 1] + s2.codePointAt(j - 1);
        }

        // 状态转移
        for (int i = 1; i <= n; i++) {
            int code1 = s1.codePointAt(i - 1);
            for (int j = 1; j <= m; j++) {
                int code2 = s2.codePointAt(j - 1);
                if (code1 == code2) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j] + code1, f[i][j - 1] + code2);
                }
            }
        }
        return f[n][m];
    }
}

718. 最长重复子数组

public class Solution718 {
    public int findLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        // f[i][j] 表示 nums1 前 i 个元素且以 i 结尾与 nums2 前 j 个元素且以 j 结尾的最长重复子数组
        int[][] f = new int[n + 1][m + 1];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int num1 = nums1[i - 1];
            for (int j = 1; j <= m; j++) {
                int num2 = nums2[j - 1];
                if (num1 == num2) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = 0;
                }
                max = Math.max(max, f[i][j]);
            }
        }
        return max;
    }
}

---

72. 编辑距离

public class Solution72 {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // f[i][j] 表示 word1 前 i 个字母与 word2 前 j 个字母的编辑距离
        int[][] f = new int[n + 1][m + 1];

        // 初始状态
        for (int i = 1; i <= n; i++) {
            f[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            f[0][j] = j;
        }

        // 状态转移
        for (int i = 1; i <= n; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    // 在 word1 插入，在 word2 插入，替换一个
                    f[i][j] = Math.min(f[i - 1][j] + 1, Math.min(f[i][j - 1] + 1, f[i - 1][j - 1]));
                } else {
                    f[i][j] = Math.min(f[i - 1][j] + 1, Math.min(f[i][j - 1] + 1, f[i - 1][j - 1] + 1));
                }
            }
        }
        return f[n][m];
    }
}

44. 通配符匹配

public class Solution44 {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();

        // f[i][j] 表示字符串 s 的前 i 个元素和字符串 p 的前 j 个元素是否能匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 1; i <= m; ++i) {
            if (p.charAt(i - 1) == '*') {
                f[0][i] = true;
            } else {
                break;
            }
        }
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 1] || f[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[n][m];
    }
}

10. 正则表达式匹配

public class Solution10 {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();

        // f[i][j] 表示 s 的前 i 个元素与 p 的前 j 个元素是否能够匹配
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    // 如果 p 的第 j 个字符是一个小写字母，那么我们必须在 s 中匹配一个相同的小写字母
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[n][m];
    }

    private boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

（全文完）