最长公共子序列LCS类的问题
概述
最长公共子序列（LCS）是字符串动态规划算法里比较经典的问题了。
该问题如下：
给定两个字符串，如abcd 和 cdab，求解出最长公共子序列的长度。
首先需要定义清楚什么是子序列？举个例子，在abcd中，ab、ac、ad、abd都是其子序列，说白了子序列就是顺序一致，但不一定连续。而与之相对应的子串则是必须是由连续的字符所构成。
弄清楚了这个概念，那么这类问题可以分成四种，分别是：
- 最长公共子序列的长度
- 具体的最长公共子序列（可能有多个答案）
- 最长公共子串的长度（注意，这里是
子串不是子序列） - 具体的最长公共子串
然后我们对每一种情况分别进行讨论！
问题一：求最长连续公共子序列的长度
举个例子，比如：
aabaccd
abbdccda
它的最长公共子序列是abccd，它的长度为5。
定义状态dp[i][j]，其中i表示字符串1的下标，j表示字符串2的下标，则该状态表示str1在[1,i]区间内，str2在[1,j]范围内，最长公共子序列的长度。
举个例子，比如dp[3][2]表示的是aab和ab的最长公共子序列长度。
使用这个状态，原问题可以表示为dp[len(str1)][len(str2)]。
状态转移方程为：
当 str1[i] == str2[j] 时，dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
则代码为：
private static int lcs1(String s1, String s2) {
char[] s1Arrs = s1.toCharArray();
char[] s2Arrs = s2.toCharArray();
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i <= s1Arrs.length; i++) {
for (int j = 1; j <= s2Arrs.length; j++) {
if (s1Arrs[i - 1] == s2Arrs[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[s1.length()][s2.length()];
}
时间复杂度为O(MxN)，空间复杂度为O(MxN)，其中M=len(str1)，N=len(str2)
问题二：求具体的最长公共子序列
在这个问题中，需要求出具体的子序列，而不仅仅是长度，同时也要注意，子序列可能有多个，不止一个。
比如：
abcd
cdab
它的最长公共子序列是ab和cd，长度都为2。
解决这个问题的基础还是需要在之前的基础上进行，意思也就是在问题一中求解出来了状态dp数组，如果根据这个数组把我们的子串给回溯回来。
那么针对上述的例子，我们可以求解出dp(5x5)数组为：
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0 1 1 1 2
0 1 2 2 2
可以看到右下角是上一个问题的答案，那么如何根据这个数组回溯出原子串呢？
首先，对于一个位置(i,j)来说，只有它是从斜对面来的，才是公共子串的一部分
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0 1 1 1 2
0 1 2 2 2
比如上面这个数组中加粗的部分，我们知道加粗部分的右下角的2是从斜对面来的，因为它周边的都是1，只有它最大，所以必然是1+1=2。所以可以看出d必然是一个子串中的字符。
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
这也就说明了，只要在一次回溯中，串起来所有是斜对面过来的位置对应的字符，即可找到子串了。
但我们也知道，并不是所有的都来dp自于斜对面，在上面的状态转移方程中，我们知道，当两个字符串当前字符不相等时，dp[i][j]还可能来自于dp[i-1][j]和dp[i][j-1]。所以如果不是从斜对面过来的们还需要走回去。
所以用加粗表示出来了上面例子一组回溯的过程，这组回溯最终得出的子串是cd
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0 1 1 1 2
0 1 2 2 2
同样也发现了，在刚刚的回溯中，还有另一条路径，如下加粗所示，这一条路径找到的子串是ab。
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0 1 1 1 2
0 1 2 2 2
最终成功的找到了所有的子串，实现代码如下：
private static HashSet<String> lcs2List;
private static HashSet<String> lcs2(String s1, String s2) {
char[] s1Arrs = s1.toCharArray();
char[] s2Arrs = s2.toCharArray();
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i <= s1Arrs.length; i++) {
for (int j = 1; j <= s2Arrs.length; j++) {
if (s1Arrs[i - 1] == s2Arrs[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]);
}
}
}
lcs2List = new HashSet<>();
extractStr(dp, s1, s2, s1.length(), s2.length(), "");
return lcs2List;
}
private static void extractStr(int[][] dp, String s1, String s2, int cols, int rows, String result) {
if (dp[cols][rows] == 0) {
lcs2List.add(result);
return;
}
if (dp[cols][rows] == dp[cols - 1][rows]) {
extractStr(dp, s1, s2, cols - 1, rows, result);
}
if (dp[cols][rows] == dp[cols][rows - 1]){
extractStr(dp, s1, s2, cols, rows - 1, result);
}
if (dp[cols][rows] != dp[cols - 1][rows] && dp[cols][rows] != dp[cols][rows - 1]) {
extractStr(dp, s1, s2, cols - 1, rows - 1, s1.toCharArray()[cols - 1] + result);
}
}
问题三：求最长连续公共子串的长度
在这个问题中，需要注意，求的是连续公共子串，关于这个定义在前面以及介绍过了，再用问题一中的例子来看一下：
aabaccd
abbdccda
我们也知道了，它的最长公共子序列长度是5，但是如果是连续子串，很容易可以发现，ccd是满足条件的，所以长度也就是3了。
同样我们写出状态和状态转移方程：
定义状态dp[i][j]，其中i表示字符串1的下标，j表示字符串2的下标，则该状态表示str1在[1,i]区间内，str2在[1,j]范围内，最长连续子串的长度。
状态转移方程也和问题一中的类似，唯一需要注意的是，当不相等的时候，是不能从其他几个位置继承长度过来的，因为只要不连续，长度就是0了，具体为：
当 str1[i] == str2[j] 时，dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = 0
还有一点需要注意的，就是并不一定右下角是答案了，因为右下角的元素并不一定是最大的，所以在整个数组中，出现最大的长度，即为答案：
private static int lcs3(String s1, String s2) {
char[] s1Arrs = s1.toCharArray();
char[] s2Arrs = s2.toCharArray();
int result = 0;
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i <= s1Arrs.length; i++) {
for (int j = 1; j <= s2Arrs.length; j++) {
if (s1Arrs[i - 1] == s2Arrs[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return result;
}
可以看出时间复杂度是O(MxN)，空间复杂度也是O(MxN)。
问题四：具体的最长公共子串
这个问题不像问题二中那么麻烦了，原因在于，加入dp[i][j]=3是答案，并且我们知道找的是连续的子串，而且长度都知道了是3，那么我们从当前位置向前寻找2个长度，构成的即为答案，所以代码如下：
private static HashSet<String> lcs4(String s1, String s2) {
char[] s1Arrs = s1.toCharArray();
char[] s2Arrs = s2.toCharArray();
int result = 0;
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 1; i <= s1Arrs.length; i++) {
for (int j = 1; j <= s2Arrs.length; j++) {
if (s1Arrs[i - 1] == s2Arrs[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
HashSet<String> resultList = new HashSet<>();
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
if (dp[i][j] == result) {
// 这里坐标可以带入一个具体的进行计算得出结果
// abcd 和 bcda
// i=4，真实是(1,4)
resultList.add(s1.substring(i - result, i));
}
}
}
return resultList;
}
}
以上是LCS类的四个问题！
