Longest common Substring
Anonymous User
775
Dynamic ProgrammingInterview

Hi,
I am solving longest common substring problem using recursion, but it is failing. I checked my logic with online available solution, but still not able to figure out the problem. If you can find the problem please write it, it will be of great help.

class Solution{
    int[][] dp;
    
    private int solve(String s1, String s2, int n, int m) {
        if (n == 0 || m == 0) {
            dp[n][m] = 0;
            return dp[n][m];
        }
        
        if (dp[n][m] != -1) {
            return dp[n][m];
        }
        
        if (s1.charAt(n - 1) == s2.charAt(m - 1)) {
            dp[n][m] = 1 + solve(s1, s2, n - 1, m - 1);
        } else {
            solve(s1, s2, n - 1, m);
            solve(s1, s2, n, m - 1);
            dp[n][m] = 0;
        }
		return dp[n][m];
    }
    int longestCommonSubstr(String S1, String S2, int n, int m){
        dp = new int[n + 1][m + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        
        solve(S1, S2, n, m);
        int ans = 0;
        
        for (int[] row : dp) {
            for (int val : row) {
                ans = Math.max(ans, val);
            }
        }
        
        return ans;
    }
}
Comments (3)