Q33 Edit Distance - LeetCode 72

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length() , n = word2.length();

        return solve(word1 , word2 , m , n ,new Integer[m+1][n+1] );
        

        /* every cell stores minimum cost needed to convert string till that row to
        string till that coloumn 
        */
    
        int dp[][] = new int [m+1][n+1];

        //base case filling first row and coloumn
        for(int j = 0 ; j < dp[0].length ; j++)
        dp[0][j] = j;

        for(int i = 0 ; i < dp.length ; i++)
        dp[i][0] = i;


        for(int i = 1 ; i < dp.length ; i++){

            for(int j = 1 ; j < dp[0].length ;j++){

                if(word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];

                else{
                    //replace
                    int replace = dp[i-1][j-1];
                    
                    //delete
                    int delete = dp[i-1][j];
                    
                    //insert
                    int insert = dp[i][j-1];

                    //find min and add 1 for your own operation
                    dp[i][j] = Math.min(replace ,Math.min(delete , insert)) +1;
                }
            }
        }

        return dp[m][n];
    }
    
    //Recursion->3^m * 3^n Memo -> m*n | Sc- m*n + m+n(stack height)
    public int solve(String w1 , String w2 , int i , int j , Integer[][]dp ){
        if(j == 0 ) //if i remains , you have to delete i characters to make w1
        return i;

        if(i == 0)  //if j remains , you have to inser j characters to make w2
        return j;

        if(dp[i][j] != null)
        return dp[i][j];

        //1 based indexing to handle base case better when turned to tabulization
        char ch1 = w1.charAt(i-1) , ch2 = w2.charAt(j-1);   

        if(ch1 == ch2)
        return dp[i][j] = 0 + solve(w1 , w2 , i-1 , j-1 , dp);

        else{
            int insert = solve(w1 ,w2 , i,j-1,dp);
            int delete = solve(w1 , w2 , i-1 , j , dp);
            int replace = solve(w1 , w2 , i-1 , j-1 , dp);

            return dp[i][j] =  1 + Math.min(insert , Math.min(delete , replace));
        }
        
    }
}