每日一题 1143最长公共子序列（LCS）（灵神版本）

本文主要是介绍每日一题 1143最长公共子序列（LCS）（灵神版本），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。
示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

题解

回溯三问

当前操作：考虑s[i]和t[j]选或不选
子问题：前i个和前j个的LCS
下一个子问题：前i-1个和前j-1个；前i个和前j-1个；前i-1个和前j个

可以得到：
s[i] = t[j]时，dfs(i,j)=max(dfs(i,j-1),dfs(i-1,j),dfs(i-1,j-1)+1)
不满足s[i] = t[j]时，dfs(i,j)=max(dfs(i,j-1),dfs(i-1,j),dfs(i-1,j-1))

两个问题：
s[i] = t[j]时，需要dfs(i,j-1),dfs(i-1,j)吗？答案是否定的
举个例子:
s=abcdc,t=abc,此时c都选,相当于s=abcd,t=ab的LCS(x)+1,此时dfs(i-1,j-1),
如果s=abcd,t=abc更优dfs(i,j-1),那么此时dfs(i,j-1)>x+1,
接下来s=abd,t=ab的LCS大于x,又因为此时的s,t为s=abcd,t=ab的子序列，所以s=abd,t=ab的LCS一定小于等于x,所以相互矛盾
不满足s[i] = t[j]时，需要dfs(i-1,j-1)吗同样也是不需要的
dfs(i-1,j-1)的答案是包含在dfs(i,j-1)之中的，即dfs(i,j-1)>=dfs(i-1,j-1)

记忆化搜索

class Solution {private char[] s,t;private int[][] cache;public int longestCommonSubsequence(String text1, String text2) {s = text1.toCharArray();t = text2.toCharArray();int n = s.length;int m = t.length;cache = new int[n][m];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1, m - 1);}public int dfs(int i, int j) {if (i < 0 || j < 0) {return 0;}if (cache[i][j] != -1) {return cache[i][j];}if (s[i] == t[j]) {return cache[i][j] = dfs(i - 1,j - 1) + 1;}return cache[i][j] = Math.max(dfs(i - 1, j),dfs(i, j - 1));}
}

递推

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] s = text1.toCharArray();char[] t = text2.toCharArray();int n = s.length;int m = t.length;int[][] f = new int[n + 1][m + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] + 1 :Math.max(f[i + 1][j], f[i][j + 1]);}}return f[n][m];}
}

空间优化

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] t = text2.toCharArray();int m = t.length;int[] f = new int[m + 1];for (char x : text1.toCharArray()) {for (int j = 0, pre = 0; j < m; j++) {int temp = f[j + 1];f[j + 1] = x == t[j] ? pre + 1 : Math.max(f[j + 1], f[j]);pre = temp;}}return f[m];}
}