The Longest Common Subsequence Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Longest Common Subsequence
  5. Discussions

The Longest Common Subsequence

Sort 145 Discussions, By:

  • ganavi552
     + 0 comments

    vector longestCommonSubsequence(vector a, vector b) { int m=a.size(); int n=b.size(); int t[m+1][n+1]; for(int i=0;i ans; while(i>0 && j>0){ if(a[i-1]==b[j-1]){ ans.push_back(a[i-1]); i--; j--; } else{ if(t[i][j-1]>t[i-1][j]){ j--; } else{ i--; } } } reverse(ans.begin(),ans.end()); return ans; }

  • minhduc_apr18
     + 0 comments
    • list1 [3, 9, 8, 3, 9, 7, 9, 7, 0]
    • list2 [3, 3, 9, 9, 9, 1, 7, 2, 0, 6]
    • result [3, 3, 9, 9, 7, 0] why this testcase true?

  • sumesh1999
     + 0 comments

    Simple C++ solution with recursion instead of iteration for dp. 

    int cache[101][101];

int lcs(vector<int> &a,vector<int> &b,int i,int j){
    if(i==0 || j==0){
        return 0;
    }
    
    if(a[i-1]==b[j-1]){
        return cache[i][j] = 1 + lcs(a, b, i-1, j-1);
    }
    
    if(cache[i][j]!=-1){
        return cache[i][j];
    }
    
    return cache[i][j] = max(lcs(a, b, i, j-1),lcs(a, b, i-1, j));
}

vector<int> longestCommonSubsequence(vector<int> a, vector<int> b) {
    
    vector<int> res;
    int i=a.size(),j=b.size();
    
    memset(cache,-1,sizeof(cache));
    
    lcs(a,b,a.size(),b.size());
    
    while(i>0 && j>0){
        if(a[i-1]==b[j-1]){
            res.push_back(a[i-1]);
            i--;
            j--;
        }else if(cache[i][j-1]>cache[i-1][j]){
            j--;
        }else{
            i--;
        }
        
    }
    reverse(res.begin(), res.end());
    return res;
}

  • Asr_codes57
     + 0 comments

    A simple python 3 Dp solution which will pass all the test cases Note: In the main function change fptr.write(' '.join(map(str, result))) to fptr.write(''.join(map(str, result))) basically remove extra space while joining just to match the output of large test cases.

    def longestCommonSubsequence(a, b):
    # Write your code here
    m=len(a)
    n=len(b)
    dp=[]
    
    for i in range(m+1):
        dp.append([])
        for j in range(n+1):
            dp[i].append((0,''))
                
    for i in range(1,m+1):
        for j in range(1,n+1):
            if a[i-1]==b[j-1]:
                dp[i][j]=(1+dp[i-1][j-1][0],dp[i-1][j-1][1]+' '+str(a[i-1]))   
            else:
                if dp[i-1][j][0]>dp[i][j-1][0]:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i][j-1]
                    
    return dp[-1][-1][-1][1:]

  • Asr_codes57
     + 0 comments

    A simple python 3 Dp solution which will pass all the test cases

    def longestCommonSubsequence(a, b):
    # Write your code here
    m=len(a)
    n=len(b)
    dp=[]
    
    for i in range(m+1):
        dp.append([])
        for j in range(n+1):
            dp[i].append((0,''))
                
    for i in range(1,m+1):
        for j in range(1,n+1):
            if a[i-1]==b[j-1]:
                dp[i][j]=(1+dp[i-1][j-1][0],dp[i-1][j-1][1]+' '+str(a[i-1]))   
            else:
                if dp[i-1][j][0]>dp[i][j-1][0]:
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i][j-1]
                    
    return dp[-1][-1][-1][1:]
Load more conversations