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

        int dp[][] = new int [m+1][n+1];

        /* every cell stores minimum cost needed to convert string till that row to
        string till that coloumn 
        */
        
        //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];
    }
}