Recursive and memorization solution for longest common substring.
i think this what you are looking for
class Solution {
int ans = 0;
public int findLength(int[] A, int[] B) {
int dp[][] = new int[A.length + 1][B.length + 1];
for (int i = 0; i < A.length + 1; i++)
Arrays.fill(dp[i], -1);
commonSub(A, B, A.length, B.length, dp);
return ans;
}
public int commonSub(int[] x, int[] y, int n, int m, int[][] dp) {
//Base conditon
if (n == 0 || m == 0) return 0;
//Memorisation
if (dp[n][m] != -1) return dp[n][m];
// for traversing the whole string n*m
commonSub(x, y, n, m - 1, dp);
commonSub(x, y, n - 1, m, dp);
if (x[n - 1] == y[m - 1]) {
dp[n][m] = commonSub(x, y, n - 1, m - 1, dp) + 1;
ans = Math.max(ans, dp[n][m]);
return dp[n][m];
}
return dp[n][m] = 0;
}
}
3 variable memorization index1 and index2 and count (cause we carrying count also)
import java.util.*;
import java.io.*;
public class Solution {
public static int lcs(String str1, String str2) {
int l1 = str1.length(), l2 = str2.length(), lmin = Math.min(l1, l2);
int[][][] dp = new int[l1][l2][lmin];
// filling 3d matrix dp with -1 for not visted
for (int[][] mat: dp) {
for (int[] row: mat)
Arrays.fill(row, -1);
}
// max unit array just for storing max value in traversal
int[] max = {0};
lcsUtil(dp, max, str1, str2, l1 - 1, l2 - 1, 0);
//returning maximum we caputured in the traversal
return max[0];
}
static int lcsUtil(int[][][] dp, int[] max, String s1, String s2, int l1, int l2, int cnt) {
if (l1 < 0 || l2 < 0)
return cnt;
if (dp[l1][l2][cnt] != -1)
return dp[l1][l2][cnt];
int x1 = 0, x2 = 0, x3 = 0;
x1 = lcsUtil(dp, max, s1, s2, l1 - 1, l2, 0);
x2 = lcsUtil(dp, max, s1, s2, l1, l2 - 1, 0);
if (s1.charAt(l1) == s2.charAt(l2)) {
x3 = lcsUtil(dp, max, s1, s2, l1 - 1, l2 - 1, cnt + 1);
max[0] = Math.max(max[0], cnt + 1);
}
return dp[l1][l2][cnt] = Math.max(x3, Math.max(x1, x2));
}
}
