面试算法题精讲：最长公共子序列
题面
题目来源：1143. 最长公共子序列
题目描述：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列（LCS）的长度。如果不存在公共子序列 ，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
解法1：记忆化搜索
代码：
// 记忆化搜索
class Solution
{
public:
int longestCommonSubsequence(string s, string t)
{
int n = s.length(), m = t.length();
int memo[n][m];
memset(memo, -1, sizeof(memo)); // -1 表示没有访问过
function<int(int, int)> dfs = [&](int i, int j) -> int
{
if (i < 0 || j < 0)
return 0;
int &res = memo[i][j];
if (res != -1)
return res;
if (s[i] == t[j])
return res = dfs(i - 1, j - 1) + 1;
return res = max(dfs(i - 1, j), dfs(i, j - 1));
};
return dfs(n - 1, m - 1);
}
};
结果：
复杂度分析：
时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。
空间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。
解法2：动态规划
代码：
// 动态规划
class Solution
{
public:
int longestCommonSubsequence(string text1, string text2)
{
// 特判
if (text1.empty() || text2.empty())
return 0;
int len1 = text1.size(), len2 = text2.size();
// 状态数组，并初始化
// dp[i][j]表示到text1的位置i为止、到text2的位置j为止、最长的公共子序列长度
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
// 状态转移
for (int i = 1; i <= len1; i++)
for (int j = 1; j <= len2; j++)
{
if (text1[i - 1] == text2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
return dp[len1][len2];
}
};
结果：
复杂度分析：
时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。
空间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。
解法3：动态规划：空间优化
代码：
// 动态规划：空间优化
class Solution
{
public:
int longestCommonSubsequence(string s, string t)
{
int n = s.length(), m = t.length(), dp[2][m + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (s[i] == t[j])
dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
else
dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
}
return dp[n % 2][m];
}
};
结果：
复杂度分析：
时间复杂度：O(nm)，其中 m 和 n 分别是字符串 s 和 t 的长度。
空间复杂度：O(nm)，其中 m 是字符串 t 的长度。
进阶：求最长公共子序列的内容
前面我们只是通过动态规划求得了两个字符串的最长公共子序列长度。我们要怎么样根据dp得到我们想要的LCS序列字符数组呢？
原理：由于我们填表的时候，当找到一个公共字符我们就会将dp[i][j]的值设置为dp[i-1][j-1] + 1的值，那么这个值也就是我们根据dp表找公共子序列的那个字符。
图解：
寻找字符的过程：
- 从 dp[m][n] 开始回溯;
- 如果 dp[i][j] == dp[i-1][j-1] + 1（即dp[i][j] != dp[i-1][j] && dp[i][j] != dp[i][j-1]），说明 s[i-1] == t[j-1]，我们找到了一个公共字符，插入lcs中，i–，j–，往左上角回溯；
- 否则，如果 dp[i][j] == dp[i-1][j]，i–，往上回溯；如果 dp[i][j] == dp[i][j-1]，j–，往左回溯。
- 由于lcs是逆序插入公共字符的，我们把lcs倒序一下，lcs就是最长公共子序列字符串了。
最终情况：
《算法导论》中回溯输出最长公共子序列过程：
实现代码：
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s = "ABCABCDEFG";
string t = "ABXYZCCDEXYZ";
int n = s.size(), m = t.size();
// dp[i][j]表示到s的位置i为止、到t的位置j为止、最长的公共子序列长度
vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
// 状态转移
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
int lscLen = dp[n][m];
cout << lscLen << endl;
string lsc = string(lscLen, 0);
int i = n, j = m, k = lscLen, idx = 0;
while (k)
{
if (dp[i][j] == dp[i - 1][j])
i--;
else if (dp[i][j] == dp[i][j - 1])
j--;
else
{
lsc[idx++] = s[i - 1];
i--;
j--;
k--;
}
}
reverse(lsc.begin(), lsc.end());
cout << lsc << endl;
system("pause");
return 0;
}
我们还可以把整个过程包装成一个函数：
string longestCommonSubsequence(string s, string t)
{
// 特判
if (s.empty() || t.empty())
return 0;
int n = s.size(), m = t.size();
// dp[i][j]表示到s的位置i为止、到t的位置j为止、最长的公共子序列长度
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
// state
vector<vector<int> > state(n + 1, vector<int>(m + 1));
// 初始化
for (int i = 0; i <= n; i++)
dp[i][0] = 0;
for (int j = 0; j <= m; j++)
dp[0][j] = 0;
// 状态转移
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (s[i - 1] == t[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
state[i][j] = 0; // 为了后面回溯，作为公共子序列的判定
}
else if (dp[i - 1][j] >= dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
state[i][j] = 1; // 为了后面向上回溯，向上寻找子序列的判定
}
else
{
dp[i][j] = dp[i][j - 1];
state[i][j] = 2; // 为了后面向左回溯，向左寻找子序列的判定
}
}
int lscLen = dp[n][m];
string lsc = string(lscLen, 0);
int i = n, j = m, k = lscLen - 1;
while (k >= 0)
{
if (state[i][j] == 0) // 找到了公共字符，往左上回溯
{
lsc[k--] = s[i - 1];
i--;
j--;
}
else if (state[i][j] == 1) // 向上回溯
i--;
else // 向左回溯
j--;
}
return lsc;
}
在动态规划求LCS的长度时，用state数组标记转移状态，在求LCS时参考state就能知道往哪个方向回溯了。
参考
- https://blog.csdn.net/weixin_54408360/article/details/126925084
- https://blog.csdn.net/lxt_Lucia/article/details/81209962
- https://blog.csdn.net/2301_77329667/article/details/136479874
