1143-Longest-Common-Subsequence.java

//memoized version

classSolution {

publicintlongestCommonSubsequence(Stringtext1, Stringtext2) {
int[][] dp = newint[text1.length()][text2.length()];
returnLCS(text1, text2, 0, 0, dp);
 }

publicintLCS(Strings1, Strings2, inti, intj, int[][] dp) {
if (i >= s1.length() || j >= s2.length()) return0; elseif (
dp[i][j] != 0
 ) returndp[i][j]; elseif (s1.charAt(i) == s2.charAt(j)) return (
1 + LCS(s1, s2, i + 1, j + 1, dp)
 ); else {
dp[i][j] =
Math.max(LCS(s1, s2, i + 1, j, dp), LCS(s1, s2, i, j + 1, dp));
returndp[i][j];
 }
 }
}

// Iterative version
classSolution {

publicintlongestCommonSubsequence(Stringtext1, Stringtext2) {
//O(n*m)/O(n*m) time/memory
if (text1.isEmpty() || text2.isEmpty()) {
return0;
 }

int[][] dp = newint[text1.length() + 1][text2.length() + 1];

for (inti = 0; i <= text1.length(); i++) {
dp[i][0] = 0;
 }

for (intj = 0; j <= text2.length(); j++) {
dp[0][j] = 0;
 }

for (inti = 1; i <= text1.length(); i++) {
for (intj = 1; j <= text2.length(); j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
 } else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
 }
 }
 }

returndp[text1.length()][text2.length()];
 }
}