hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Longest Common Subsequence


  • Approach:

    1. Initiate a 2D matrix lcs to hold the LCS length between substring indexed (0 ~ i) < |text1| for text1 and substring indexed (0 ~ j) < |text2|, where |S| = size of the string S.

    2. Run a loop for each character of text1.

    3. Run another loop nested to the previous one for each character of text2.

    4. If ith character of text1 is equal to the jth character of text2 then -
      lcs[i][j] = lcs[i-1][j-1] + 1

    5. If not equal then -
      lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])

    6. Return lcs[m][n] where m = size of text1 and n = size of text2.


  • Time and Space Complexity:

      • Time Complexity: O(M x N)

      • Space Complexity: O(M x N)


Code [C++]

class Solution {

public:

int longestCommonSubsequence(string text1, string text2) {

int text1_len = text1.size(), text2_len = text2.size();

int lcs[text1_len+1][text2_len+1];

memset(lcs, 0, sizeof(lcs));

for(int i=1; i<=text1_len; i++){

for(int j=1; j<=text2_len; j++){

if(text1[i-1] == text2[j-1]){

lcs[i][j] = lcs[i-1][j-1] + 1;

}

else{

lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);

}

}

}

return lcs[text1_len][text2_len];

}

};