Edit distance

Problem

TC : O(n*m)
SC : O(n+m)( recursive stack space) + O(n*m)(dp array)

class Solution {
    public int editDistance(String str1, String str2) {
        // Code here
        int dp[][] = new int[str1.length()][str2.length()];
        for(int d[] : dp) Arrays.fill(d,-1);
        return minop(0,0,str1,str2,dp);
    }
    public int minop(int i, int j , String a,String b, int dp[][]){
        //base case
        if(i==a.length() && j!=b.length()) return b.length()-i;
        if(j ==b.length() && i!=a.length()) return a.length()-j;
        if(i ==a.length() && j ==b.length()) return 0;

        if(dp[i][j]!=-1) return dp[i][j];
        //if match increment both the indexes
        if(a.charAt(i) == b.charAt(j)){
            return dp[i][j] =  minop(i+1,j+1,a,b,dp);
        }
        else{
            //if not match we will have to perform 1 operation either remove the char at index i ( then i will go to next char in a: i+1)
            // or insert char at index i, ( insert the same char which is present at j in b,) resulting in i staying at the same index
            //, and j = j+1( since the inserted char at i in a matched with char at j in b)
            //or replace char at i in a with the same char at j in b, hence i will go to next char in a at i+1, j will go to next char at j +1

            return dp[i][j] =  1 + 
            Integer.min(minop(i+1,j,a,b,dp),Integer.min(minop(i+1,j+1,a,b,dp),minop(i,j+1,a,b,dp)));
        }
    }
}