08 - Longest Common Subsequence - Final DP solution in Java
@backstreetbrogrammer
Dynamic Programming Playlist: • Dynamic Programming
Java Serialization Playlist: • Java Serialization
-------------------------------------------------------------------------------------------------------
Final solution in Java and submission results in Leetcode.
Pseudo code:
int[][] dp = new int[row + 1][col + 1];
for (int i = row - 1; i greater than or equal to 0; i--) {
for (int j = col - 1; j greater than or equal to 0; j--) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[i][j] = 1 + dp[i + 1][j + 1];
} else {
dp[i][j] = MAX(dp[i][j + 1], dp[i + 1][j]);
}
}
}
return dp[0][0];
Time complexity: O(text1.length * text2.length)
Space complexity: O(text1.length * text2.length)
Github: https://github.com/backstreetbrogramm...
Leetcode: https://leetcode.com/problems/longest...
#java #javadevelopers #javaprogramming #algorithms #datastructuresandalgorithms #dynamicprogramming #onemonthofdynamicprogramming