Two solution Recursive with memo and DP Solution Java


#1

Recursive :slight_smile:

public class Solution {
    int findLcs(int i, int j, String a, String b, int[][] dp) {
          if( i < 0 || j < 0) {
            return 0;
        } 
        if(dp[i][j] >= 0) return dp[i][j];
        if(a.charAt(i) == b.charAt(j)) {
            dp[i][j] = Math.max(dp[i][j],1+findLcs(i-1,j-1,a,b,dp));
        } else{
            dp[i][j] = Math.max(dp[i][j],Math.max(findLcs(i-1,j,a,b,dp), findLcs(i,j-1,a,b,dp)));
        }
        return dp[i][j];
    }
    public int solve(String a, String b) {
        int n = a.length(), m = b.length();
        if(n < 0 || m < 0) return 0;
        int[][] dp = new int[n][m];
        for(int i = 0;i<n;i++) {
        Arrays.fill(dp[i],-1);
        }
        return findLcs(n-1,m-1,a,b,dp);
    }
}

Iterative :slightly_smiling_face:

public class Solution {
    public int solve(String a, String b) {
    int n = a.length(), m = b.length();
    if(n < 0 || m < 0) return 0;
    int dp[][] = new int[n+1][m+1];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) {
        if(a.charAt(i-1) == b.charAt(j-1)) {
            dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
        } else {
            dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i][j-1]));
        }
    }
    return dp[n][m];
    }
}