Skip to content

Longest common subsequence type problem

description

  • you are given an two array or and string
  • to compare two ends of string and make some choice

recursive code

#include <bits/stdc++.h>
using namespaces std;

// state is represented by (m, n)
// m - 1 th item and n-1 th item
int lcs(string X, string Y, int m, int n ){
    // base case, we reached the end
    if (m == 0 || n == 0) return 0;

    // if both are equal
    if (X[m-1] == Y[n-1]) 
        return 1 + lcs(X, Y, m-1, n-1);
    else 
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

int main(){
    string s1 = "hithisisthis";
    string s2 = "hithias";
    cout << lcs(s1, s2, s1.length(), s2.length());
    return 0;
}

memoization sol

#include <bits/stdc++.h>
using namespaces std;

// cache for results of state (m, n)
vector<vector<int>> dp;

int lcs(string X, string Y, int m, int n ){
    if (m == 0 || n == 0) return 0;
    // get results form cache
    if(dp[m][n]!=-1) return dp[m][n];
    if (X[m-1] == Y[n-1]) return dp[m][n] = 1 + lcs(X, Y, m-1, n-1);
    else return dp[m][n] = max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

int main(){
    string s1 = "hithisisthis";
    string s2 = "hithias";
    dp = vector<vector<int>> (s1.length()+1, vector<int>(s2.length()+1, -1));
    cout << lcs(s1, s2, s1.length(), s2.length());
    return 0;
}

top down approach

#include <bits/stdc++.h>
using namespaces std;

int lcs(string X, string Y, int m, int n ){
    vector<vector<int>> dp(s1.length()+1, vector<int>(s2.length()+1, 0));

    // base case already initialized

    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
            if(X[m-1] == X[n-1]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[m][n];
}

int main(){
    string s1 = "hithisisthis";
    string s2 = "hithias";
    cout << lcs(s1, s2, s1.length(), s2.length());
    return 0;
}

practice problems