Massive Algorithms: LintCode 762 - Longest Common Subsequence II

LintCode 762 - Longest Common Subsequence II

Given two sequence P and Q of numbers. The task is to find Longest Common Subsequence of two sequence if we are allowed to change at most k element in first sequence to any value.

Example

Given P = [8 ,3], Q = [1, 3], K = 1

Return 2

Given P = [1, 2, 3, 4, 5], Q = [5, 3, 1, 4, 2], K = 1

Return 3

https://www.geeksforgeeks.org/longest-common-subsequence-with-at-most-k-changes-allowed/

The idea is to use Dynamic Programming. Define a 3D matrix dp[][][], where dp[i][j][k] defines the Longest Common Subsequence for the first i numbers of first array, first j number of second array when we are allowed to change at max k number in the first array.
Therefore, recursion will look like

If P[i] != Q[j], 
    dp[i][j][k] = max(dp[i - 1][j][k], 
                      dp[i][j - 1][k], 
                      dp[i - 1][j - 1][k - 1] + 1) 
If P[i] == Q[j], 
    dp[i][j][k] = max(dp[i - 1][j][k], 
                      dp[i][j - 1][k], 
                      dp[i - 1][j - 1][k] + 1)

Time Complexity: O(N*M*K).

int lcs(int dp[MAX][MAX][MAX], int arr1[], int n, 

                       int arr2[], int m, int k) 

{

    // If at most changes is less than 0. 

    if (k < 0) 

        return -1e7; 

    // If any of two array is over. 

    if (n < 0 || m < 0) 

        return 0; 

    // Making a reference variable to dp[n][m][k] 

    int& ans = dp[n][m][k]; 

    // If value is already calculated, return 

    // that value. 

    if (ans != -1) 

        return ans; 

    // calculating LCS with no changes made. 

    ans = max(lcs(dp, arr1, n - 1, arr2, m, k),  

              lcs(dp, arr1, n, arr2, m - 1, k)); 

    // calculating LCS when array element are same. 

    if (arr1[n] == arr2[m]) 

        ans = max(ans, 1 + lcs(dp, arr1, n - 1,  

                                arr2, m - 1, k)); 

    // calculating LCS with changes made. 

    ans = max(ans, 1 + lcs(dp, arr1, n - 1,  

                          arr2, m - 1, k - 1)); 

    return ans; 

}

https://www.jiuzhang.com/solution/longest-common-subsequence-ii/
最长公共子串的问题是典型的动态规划题，在这里已有题解，就是用二维矩阵来存储所有的中间最佳状态。
这是这个题的变种，因为第一个字符串可以进行k次变动。那么解体就得用三维矩阵来存储中间最佳状态。
而且要把k=0的情况拿出来单独解决。这个k=0的情况实际上就是无变动情形下的解。这个的时间复杂度
是O(mnk)，m和n是P和Q字符串的长度，k是P可变换元素数量。

    def longestCommonSubsequence2(self, P, Q, k):
        # Write your code here
        m = len(P)
        n = len(Q)
        l = [[[None for g in range(k+1)] \
        for j in range(n+1)] for i in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i == 0 or j == 0:
                    l[i][j][0] = 0
                elif P[i-1] == Q[j-1]:
                    l[i][j][0] = l[i-1][j-1][0] + 1
                else:
                    l[i][j][0] = max(l[i-1][j][0], l[i][j-1][0])
        for i in range(m+1):
            for j in range(n+1):
                for g in range(1, k+1):
                    if i == 0  or j == 0:
                        l[i][j][g] = 0
                    elif P[i-1] != Q[j-1]:
                        l[i][j][g] = max(l[i-1][j][g], l[i][j-1][g], l[i-1][j-1][g-1] + 1)
                    else:
                        l[i][j][g] = max(l[i-1][j][g], l[i][j-1][g], l[i-1][j-1][g] + 1)
        return l[m][n][k]

https://blog.csdn.net/zhaohengchuan/article/details/79703980
dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度。初始化之后，对于dp[i][j][t]，如果P[i-1]=Q[j-1]，由于t表示改变t个元素，dp[i][j][t]可能取dp[i-1][j-1][t]+1，在P[i-1]!=Q[j-1]时，dp[i][j][t]可能取dp[i-1][j-1][t-1]+1（需要改变一个元素）。由于dp[i][j][t]还可能取dp[i-1][j][t]和dp[i][j-1][t]，最终结果取最大值。
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
if (P.empty() || Q.empty() || k < 0)
return 0;
int lenp = P.size(), lenq = Q.size();
//dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度
vector<vector<vector<int>>> dp(lenp + 1, vector<vector<int>>(lenq + 1, vector<int>(k + 1)));
//当i = 0或j = 0时,dp[i][j][t] = 0
for (int i = 0; i <= lenp; ++i)
{
for (int t = 0; t <= k; ++t)
dp[i][0][t] = 0;
}
for (int j = 0; j <= lenq; ++j)
{
for (int t = 0; t <= k; ++t)
dp[0][j][t] = 0;
}
//处理k=0的情况,类似于公共子序列
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][0] = dp[i - 1][j - 1][0] + 1;
else
dp[i][j][0] = maxVal(dp[i - 1][j][0], dp[i][j - 1][0]);
}
}
//若P[i-1]=Q[j-1],不必再变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t]+1的最大值
//否则,可能需要变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t-1]+1的最大值
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
for (int t = 1; t <= k; ++t)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t] + 1));
else
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t - 1] + 1));
}
}
}
return dp[lenp][lenq][k];
}
https://github.com/jiadaizhao/LintCode/blob/master/0762-Longest%20Common%20Subsequence%20II/0762-Longest%20Common%20Subsequence%20II.cpp
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
int m = P.size();
int n = Q.size();
int dp[1 + k][1 + m][1 + n];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[0][i][j] = 1 + dp[0][i - 1][j - 1];
}
else {
dp[0][i][j] = max(dp[0][i - 1][j], dp[0][i][j - 1]);
}
}
}

for (int l = 1; l <= k; ++l) {
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[l][i][j] = 1 + dp[l][i - 1][j - 1];
}
else {
dp[l][i][j] = max({dp[l][i - 1][j], dp[l][i][j - 1], 1 + dp[l - 1][i - 1][j - 1]});
}
}
}
}

return dp[k][m][n];
}

LintCode 762 - Longest Common Subsequence II

Example

Labels

Popular Posts