Problem Statement
What is the time complexity of finding the Longest Common Subsequence (LCS) of two strings using dynamic programming?
Explanation
The Longest Common Subsequence problem has time complexity O of m times n where m and n are the lengths of the two strings. The DP table has dimensions m plus 1 by n plus 1, and we fill each cell in constant time.
The algorithm builds a 2D DP table where dp of i of j represents the length of LCS of the first i characters of string 1 and first j characters of string 2. If characters match, dp of i of j equals dp of i minus 1 of j minus 1 plus 1. Otherwise, dp of i of j equals max of dp of i minus 1 of j and dp of i of j minus 1. Space complexity is also O of m times n, though it can be optimized to O of min of m comma n.
Code Solution
SolutionRead Only
// LCS using DP - O(m*n) time and space
int longestCommonSubsequence(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// Example: s1="ABCDGH", s2="AEDFHR"
// LCS: "ADH" (length 3)
//
// DP table:
// "" A E D F H R
// "" 0 0 0 0 0 0 0
// A 0 1 1 1 1 1 1
// B 0 1 1 1 1 1 1
// C 0 1 1 1 1 1 1
// D 0 1 1 2 2 2 2
// G 0 1 1 2 2 2 2
// H 0 1 1 2 2 3 3Practice Sets
This question appears in the following practice sets:
