最近项目中需要求两个字符串(序列)的公共部分，所以查了一下相关的算法，了解到有最长公共子串、最小编辑距离等可用于计算两个字符串的相似程度，将leetcode上对应的题目做了之后，暂时按照自己的理解总结一下。
1143. 最长公共子序列(LCS)
思路： 这是经典的LCS( Longest Common Subsequence)问题，与子串不同，子序列不要求连续，只要求在原串中保持相对顺序即可
-
二维DP，状态定义： i 表示第一个串str1的[ 0 , i ]的子串，j 表示第二个串str2的[ 0 , j ] 的子串, dp[ i ] [ j ] 表示str1在[ 0 , i ]范围内和str2在[ 0 , j ]范围内的LCS
-
初始化baseCase辅助数组，第一行代表第一个串为空串时与第二个串的最长公共子序列长度(由于没有公共子序列，所以初始化为0)；第一列代表第二个串为空时与第一个串的最长公共子序列长度(同上也没有公共子序列，初始化为0)
-
状态转移方程
当str1[ i ] == str2[ j ]时，dp[ i ] [ j ] = dp[ i - 1 ] [ j - 1 ] + 1（在 str1 截止到 i - 1 的子串，str2截止到 j - 1 的子串求得的LCS基础上，新增一对相等，公共子序列长度+1)
当str1[ i ] != str2[ j ]时，dp[ i ] [ j ] = max(dp[ i - 1 ] [ j ], dp[ i ] [ j-1 ])(当遍历到 str1 当前的字符和str2当前字符对应不相等，取str1中[ 0 ， i - 1 ]范围内子串和 str2[ 0 ， j - 1 ]范围内子串求得的LCS 和 str1[ 0 , i ]范围内子串 和 str2[ 0， j - 1 ]范围内子串中求得的LCS中的最大值)
-
维护的是两个串截止当前字符子串的LCS，最后两个串的公共子序列最大值就为dp[ m ] [ n ]
在求长度的同时加上求具体最长公共子序列的内容：根据求取长度的方法反向找到当前长度的序列由哪些字符拼接，这里需要一个标志位记录当前长度的来源，可以使用数字代表方向 0 代表 ↘ (来自右下角),1 代表 ↓ (来自上方) ， 2 代表 → （来自左方），3表示来自左方和上方都有可能
注意：可能根据不同方向得到的公共序列相同，可以使用set保存便于去重
求多解的公共子序列的集合参考链接：https://blog.csdn.net/zpalyq110/article/details/79994001
class Solution {
private:
set<string> setOfLCS; //最长公共子序列的集合,使用set去重
vector<vector<int>> direction; //记录二维DP中的方向
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(),n = text2.size();
direction = vector<vector<int>>(m+1,vector<int>(n+1,0));
vector<vector<int>> dp(m+1,vector<int>(n+1,0)); //在两个串开头添加空串,初始为0
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(text1[i-1] == text2[j-1]){ //注意在原串中的索引i-1、j-1
dp[i][j] = dp[i-1][j-1] + 1;
direction[i][j] = 0; //记录长度方向来源(左上)
}else{
//如果当前的字符不相等，取text1[i]text2[j-1] text[i-1]text2[j]中的最大值
if(dp[i-1][j] > dp [i][j-1]){
dp[i][j] = dp[i-1][j];
direction[i][j] = 1; //记录长度方向来源(上)
}else if(dp[i][j-1] > dp[i-1][j]){
dp[i][j] = dp[i][j-1];
direction[i][j] = 2; //记录长度方向来源(左)
}else{
dp[i][j] = dp[i][j-1]; //长度相同，任意取一边
direction[i][j] = 3; //上和左边都可
}
}
}
}
if(dp[m][n] > 0){ //如果公共子序列的长度大于0，将其打印
string lcs; //用于保存一种公共子序列的中间变量
getLcs(m,n,text1,lcs);
for(auto s : setOfLCS){
cout << s << endl;
}
}
return dp[m][n];
}
void getLcs(int x,int y,string& text1, string lcs){
while(x > 0 && y > 0){
if(direction[x][y] == 0){
lcs = text1[x - 1] + lcs;
x--;
y--;
}else if(direction[x][y] == 1){
x--;
}else if(direction[x][y] == 2){
y--;
}else{ //两种方向分别递归求子序列
getLcs(x-1,y,text1,lcs);
getLcs(x,y-1,text1,lcs);
return;
}
}
setOfLCS.insert(lcs);
}
};
718.最长重复子数组
思路：与上一题不同的是，子数组要求连续
- 定义状态，dp[ i ] [ j ]表示 A在[ 0, i ]范围内 B在[ 0, j ] 范围内的LCS
- 状态转移，由于子数组要求连续，所以只有A在[ 0, i - 1 ]范围内与B在[ 0, j - 1]范围内的LCS, 并且当前A[i] == B[j] 才满足公共子数组条件
- 使用一个变量维护一个最大值即可
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int n = A.size(),m = B.size();
if(n == 0 || m == 0){
return {};
}
vector<vector<int> >dp(n+1,vector<int>(m+1,0));
int res = 0;
for(int i = 1;i < n+1;i++){
for(int j = 1;j < m+1;j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
res = max(res,dp[i][j]);
}
//当前元素不相等dp[i][j]为0
}
}
return res;
}
};
72.最小编辑距离
思路:编辑的状态，综合起来一共只有三种，A的删除->B的增加（上方）、A的增加->B的删除（左方），A修改->B修改（左上角）
-
定义状态，dp[ i ] [ j ]表示 str1 中 [ 0, i ]范围内的子串，str2[ 0, j ]范围内的子串最小编辑距离
-
状态转移，如果str1[ i ] == str2[ j ], dp[ i ] [ j ] = dp[ i - 1 ] [ j - 1 ]相等当前不用编辑，
str1[ i ] != str2[ j ],dp[ i ] [ j ] = min(dp[ i - 1] [ j ],dp[ i ] [ j - 1 ], dp[ i - 1 ] [ j - 1 ]) + 1 从三种状态最小的编辑次数选择一种编辑操作
-
维护的是截至到当前的最小编辑次数，所以最终的解为dp[ m ] [ n ],在两个串中都加入空字符（baseCase辅助数组）
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(),n = word2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
//定义状态dp[i][j] word1[0, i]word2[0, j]相匹配需要操作的最小次数
for(int i = 1;i <= n;i++){
dp[0][i] = i; //初始化第一行为i
}
for(int i = 1;i <= m;i++){
dp[i][0] = i; //初始化第一列为i
}
for(int i = 1;i <= m;i++){
for(int j = 1;j <= n;j++){
if(word1[i-1] == word2[j-1]){ //对应在word中索引-1
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
return dp[m][n];
}
};