The problem requires finding the length of the longest common subsequence between two
strings.
We use a
dynamic programming
to solve this.
We create a
2D array 't'
where
t[i][j]
represents the length of the longest common subsequence between the
first
'i' characters
of
'text1' and the
first
'j' characters of
'text2'.
If the characters at the current positions
match, we
increment the value from
the diagonal cell.
Otherwise, we take the maximum value
from the left or top cell.
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n = text1.size(); int m = text2.size(); int t[n+1][m+1]; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(i==0 || j==0) t[i][j]=0; else{ if(text1[i-1]==text2[j-1]) // If Characters are equals t[i][j] = 1+t[i-1][j-1]; else t[i][j] = max(t[i-1][j],t[i][j-1]); } } } return t[n][m]; } };
The algorithm iterates through each character of both strings, resulting in a time complexity of O(n * m), where n and m are the lengths of the strings.
The algorithm uses a 2D array of size (n+1) x (m+1) to store intermediate results.