【中等】最长公共子序列问题（Java）
分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter
package live.every.day.CodingInterviewGuide.RecursionAndDynamicPrograming; /** * 最长公共子序列问题 * * 【题目】 * 给定两个字符串str1和str2，返回这两个字符串的最长公共子序列。 * 子序列：不要求连续，但顺序必须一致。 * * 【难度】 * 中等 * * 【解答】 * 本题是非常经典的动态规划问题，先来介绍求解动态规划表的过程。 * * 如果str1的长度为M，str2的长度为N，生成大小为MxN的矩阵dp，行数为M，列数为N。dp[i][j]的含义是str1[0..i]与 * str2[0..j]的最长公共子序列的长度。从左到右，再从上到下计算矩阵dp。 * 1. 矩阵dp第一列即dp[0..M-1][0]，dp[i][0]的含义是str1[0..i]与str2[0]的最长公共子序列长度。str2[0]只有一个字 * 符，所以dp[i][0]最大为1。如果str1[i]==str2[0]，则令dp[i][0]=1，一旦dp[i][0]被设置为1，之后的 * dp[i+1..M-1][0]也都为1。 * 2. 矩阵dp第一行即dp[0][0..N-1]与步骤1同理，如果str1[0]==str2[j]，则令dp[0][j]=1，一旦dp[0][j]被设置为1， * 之后的dp[0][j+1..N-1]也都为1。 * 3. 对其他位置(i,j)，dp[i][j]的值只可能来自以下三种情况： * 可能是dp[i-1][j]，代表str1[0..i-1]与str2[0..j]的最长公共子序列长度。 * 可能是dp[i][j-1]，代表str1[0..i]与str2[0..j-1]的最长公共子序列长度。 * 如果str1[i]==str2[j]，还可能是dp[i-1][j-1]+1。 * 这三个可能的值中，选最大的作为dp[i][j]的值。具体过程请参看如下代码中的getDp方法。 * * dp矩阵中最右下角的值代表str1整体和str2整体的最长公共子序列的长度。通过整个dp矩阵的状态，可以得到最长公共子序列。 * 具体方法如下： * 1. 从矩阵的右下角开始，有三种移动方式：向上、向左、向左上。假设移动的过程中，i表示此时的行数，j表示此时的列数，同时 * 用一个变量res来表示最长公共子序列。 * 2. 如果dp[i][j]大于dp[i-1][j]和dp[i][j-1]，说明之前在计算dp[i][j]的时候，一定是选择了决策dp[i-1][j-1]+1， * 可以确定str1[i]等于str2[j]，并且这个字符一定属于最长公共子序列，把这个字符放进res，然后向左上方移动。 * 3. 如果dp[i][j]等于dp[i-1][j]，说明之前在计算dp[i][j]的时候，dp[i-1][j-1]+1这个决策不是必须选择的决策，向上 * 方移动即可。 * 4. 如果dp[i][j]等于dp[i][j-1]，与步骤3同理，向左方移动。 * 5. 如果dp[i][j]同时等于dp[i-1][j]和dp[i][j-1]，向上还是向左无所谓，选择其中一个即可，反正不会错过必须选择的字 * 符。 * 也就是说，通过dp求解最长公共子序列的过程就是还原出当时如何求解dp的过程，来自哪个策略就朝哪个方向移动。全部过程请参 * 看如下代码中的lcs方法。 * * 计算dp矩阵中的某个位置就是简单比较相关的3个位置的值而已，所以时间复杂度为O(1)，动态规划表dp的大小为MxN，所以计算 * dp矩阵的时间复杂度为O(MxN)。通过dp得到最长公共子序列的过程为O(M+N)，因为向左最多移动N个位置，向上最多移动M个位 * 置，所以总的时间复杂度为O(M+N)，额外空间复杂度为O(MxN)。如果题目不要求返回最长公共子序列，只想求最长公共子序列的 * 长度，那么可以用空间压缩的方法将额外空间复杂度减小为O(min{M,N})，有兴趣的读者请参看“矩阵的最小路径和”问题，这里不 * 再详述。 * * @author LiveEveryDay */ public class LongestCommonSubsequence { public static int[][] getDp(char[] str1, char[] str2) { int[][] dp = new int[str1.length][str2.length]; dp[0][0] = str1[0] == str2[0] ? 1 : 0; for (int i = 1; i < str1.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0); } for (int j = 1; j < str2.length; j++) { dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0); } for (int i = 1; i < str1.length; i++) { for (int j = 1; j < str2.length; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); if (str1[i] == str2[j]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1); } } } return dp; } public static String lcs(String str1, String str2) { if (str1 == null || str2 == null || str1.isEmpty() || str2.isEmpty()) { return ""; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int[][] dp = getDp(chs1, chs2); int m = chs1.length - 1; int n = chs2.length - 1; char[] res = new char[dp[m][n]]; int i = res.length - 1; while (i >= 0) { if (m > 0 && dp[m][n] == dp[m - 1][n]) { m--; } else if (n > 0 && dp[m][n] == dp[m][n - 1]) { n--; } else { res[i--] = chs1[m]; m--; n--; } } return String.valueOf(res); } public static void main(String[] args) { String str1 = "1A23CD4B56"; String str2 = "02B1D23A456A"; System.out.println(lcs(str1, str2)); } } // ------ Output ------ /* 123456 */