Longest Common Subsequence

lcs.cpp

// recursive version , computes many subproblems again and again 
int lcsRecursive(string& s1, string& s2, int i, int j){
    if(i >= s1.length() || j >= s2.length()) return 0;
 
    if(s1[i] == s2[j]) return 1 + lcsRecursive(s1, s2, i+1, j+1);
    else{
        return max(lcsRecursive(s1, s2, i+1, j), lcsRecursive(s1, s2, i, j+1));
    }
}

// saves results for previously computed subproblems thus reducing the recursion tree exponentially. 
int lcsBottomUp(string& s1, string& s2, int len1, int len2){
    int results[len1+1][len2+1];

    for(int i = 0; i <= len2; i++) results[0][i] = 0;
    for(int j = 0; j <= len1; j++) results[j][0] = 0;
    
    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(s1[i-1] == s2[j-1]){
                results[i][j] = 1 + results[i-1][j-1];
            }else{
                results[i][j] = max(results[i-1][j], results[i][j-1]);
            }
        }
    }
    
    return results[len1][len2];
}