Problem Statement
Explain the dynamic programming approach for finding the longest common subsequence between two strings.
Explanation
LCS is the longest sequence that appears in both strings, not necessarily contiguous. DP approach uses a 2D table dp[i][j] where dp[i][j] is the LCS length of prefixes of lengths i and j. Recurrence: if same character, dp[i][j]=1+dp[i-1][j-1]; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]). Time and space: O(m*n).
Code Solution
SolutionRead Only
int LCS(String a,String b){
int m=a.length(),n=b.length();
int[][] dp=new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n]; }Practice Sets
This question appears in the following practice sets:
