The Longest Common Subsequence (LCS) Discussions | Tutorials | HackerRank

Sort by

recency

|

24 Discussions

|

  • + 0 comments

    C# solution:

        public static string FindLcs (int[] a, int[] b)
        {
            var cache = new int[b.Length + 1, a.Length + 1];
            InitCache(cache);
            FillDpTable(cache, a, b);
            return ConstructLcsString(a, cache);
        }
        
        private static void InitCache(int[,] cache)
        {
            for (int i = 0; i < cache.GetLength(0); i++)
            {
                cache[i, 0] = 0;
            }
    
            for (int i = 0; i < cache.GetLength(1); i++)
            {
                cache[0, i] = 0;
            }
        }
        
        private static void FillDpTable(int[,] cache, int[] row, int[] col)
        {
            for (int i = 1; i <= col.Length; i++)
            {
                for (int j = 1; j <= row.Length; j++)
                {
                    if (col[i - 1] == row[j - 1])
                    {
                        cache[i, j] = 1 + cache[i - 1, j - 1];
                    }
                    else
                    {
                        cache[i, j] = Math.Max(cache[i - 1, j], cache[i, j - 1]);
                    }
                }
            }
        }
    
        private static string ConstructLcsString(int[] row, int[,] cache)
        {
            string result = "";
            int i = cache.GetLength(0) - 1;
            int j = cache.GetLength(1) - 1;
    
            while (i > 0 && j > 0)
            {
                if (cache[i, j - 1] != cache[i, j] && cache[i - 1, j] != cache[i, j])
                {
                    result = row[j - 1] + " " + result;
                    i--;
                    j--;
                }
                else if (cache[i - 1, j] == cache[i, j])
                {
                    i--;
                }
                else
                {
                    j--;
                }
            }
    
            return result.Trim();
        }
    
  • + 0 comments
    def lcs(x,y,m,n):
        t=[[0 for i in range(n+1)] for i in range(m+1)]
        
        for i in range(n+1):
            t[0][i]=0
        for i in range(m+1):
            t[i][0]=0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if x[i-1] == y[j-1]:
                    t[i][j]=1+t[i-1][j-1]
                else:
                    t[i][j]=max(t[i-1][j],t[i][j-1])
        index=t[m][n]
        i=m
        j=n
        lcs=['']*(index+1)
        lcs[index]=''
        while i > 0 and j >0:
            if x[i-1] == y[j-1]:
                lcs[index-1]=x[i-1]
                i=i-1
                j=j-1
                index=index-1
            elif t[i-1][j] > t[i][j-1]:
                i=i-1
            else:
                j=j-1
        print(' '.join(lcs))
    ab=input().split()
    x=input().split()
    y=input().split()
    m=len(x)
    n=len(y)
    lcs(x,y,m,n)
    
  • + 0 comments
    def leastCommonSequence(seq1, seq2):
        lcs = [[[] for c in range(len(seq1)+1)]for y in range(len(seq2)+1)]
        for i in range(1, len(seq2)+1):
            for j in range(1, len(seq1)+1):
                if seq1[j-1] == seq2[i -1]:
                    lcs[i][j] = lcs[i-1][j-1] + [seq2[i-1]]
                else:
                    lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1], key=len)
        return lcs[-1][-1]
    
    n, m = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    result = leastCommonSequence(a, b)
    for i in result:
            print(i, end = " ")
    
  • + 1 comment
    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    
    int main() {
        int n,m;
        cin>>n>>m;
        int multi[n+1][m+1],tracker[n+1][m+1];
        int ar[n],arr[m];
        for(int i=0;i<n;i++)
        cin>>ar[i];
        for(int j=0;j<m;j++)
        cin>>arr[j];
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(i==0||j==0)
                multi[i][j] = 0;
                else
                {
                    if(ar[i-1] == arr[j-1])
                    {
                    multi[i][j] = multi[i-1][j-1]+1;
                    tracker[i][j] = 3;
                    }
                    else
                    {
                    multi[i][j] = max(multi[i-1][j],multi[i][j-1]);
                    if(multi[i][j] == multi[i-1][j])
                    tracker[i][j] = 1;
                    else
                    tracker[i][j] = 2;
                    }
                }
            }
        }
        
        int j = m;
        vector<int> ans;
    
        for(int i=n;i>0;i--)
        {
            if(j<=0)
            break;
            if(tracker[i][j] == 1)
            {
                continue;
            }
    
            else if(tracker[i][j] == 2)
            {
                i++;
                j--;
            }
    
            else if(tracker[i][j] == 3)
            {
                j--;
                ans.push_back(arr[j]);
            }
        }
    
        for(int i=ans.size()-1;i>=0;i--)
        {
            cout<<ans[i]<<" ";
        }
    
    
    
        return 0;
    }
    
    • + 0 comments

      Easy solution

  • + 0 comments

    my python3 solution

    def lcs(a, b):
      n = len(a)
      m = len(b)
      #create dp ie. like an empty matrix
      dp = [[ [] for j in range(m+1)] for i in range(n+1)]
      #lcs logic
      for i in range(1, n+1):
        for j in range(1, m+1):
          if a[i-1] == b[j-1]:
            dp[i-1][j-1].append(a[i-1])
            dp[i][j] = dp[i-1][j-1].copy()
          else:
            temp = max(dp[i][j-1], dp[i-1][j], key = len)
            dp[i][j] = temp.copy()
      return dp[n][m]
    		
    n, m = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = list(map(int, input().split(' ')))
    result = lcs(a, b)
    for i in result:
    		print(i, end = " ")