for Robot Artificial Inteligence

66. Longest Common Subsequence

20 Aug 2020 | Daily Algorithms

  • Bottom-up DP utilizes a matrix m where we track LCS sizes for each combination of i and j.

  • If a[i] == b[j], LCS for i and j would be 1 plus LCS till the i-1 and j-1 indexes.
  • Otherwise, we will take the largest LCS if we skip a charracter from one of the string (max(m[i - 1][j], m[i][j - 1]).
  • This picture shows the populated matrix for “xabccde”, “ace” test case.

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<short>> m(text1.size()+1,vector<short>(text2.size()+1));
        for(auto i = 1; i<=text1.size();i++)
        {
            for(auto j=1; j<=text2.size();j++)
            {
                if(text1[i-1]==text2[j-1])
                {
                    m[i][j] = m[i-1][j-1]+1;
                }
                else
                {
                    m[i][j] = max(m[i-1][j],m[i][j-1]);
                }
            }
        }
        return m[text1.size()][text2.size()];
    }
};

Comments