Edit Distance

 Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character

Delete a character

Replace a character

 

Example 1:

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation: 

horse -> rorse (replace 'h' with 'r')

rorse -> rose (remove 'r')

rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation: 

intention -> inention (remove 't')

inention -> enention (replace 'i' with 'e')

enention -> exention (replace 'n' with 'x')

exention -> exection (replace 'n' with 'c')

exection -> execution (insert 'u')

 

Constraints:

0 <= word1.length, word2.length <= 500

word1 and word2 consist of lowercase English letters.

🧠 Key Idea: Recursion with Choices

At each character index (i, j) in word1 and word2:

1. ✅ If characters match, move both pointers:

word1[i] == word2[j] → no edit needed → move to i+1, j+1

1. ❌ If characters don’t match, 3 choices:

   • Insert → move j (we matched a new character to word1)

   • Delete → move i (we removed a char from word1)

   • Replace → move both (we changed word1[i] to match word2[j])

We pick the minimum of these 3.

🧾 Recursive Formula

Let dp[i][j] = min edit distance to convert word1[i:] to word2[j:]




if word1[i] == word2[j]:

    dp[i][j] = dp[i+1][j+1]

else:

    insert  = dp[i][j+1]

    delete  = dp[i+1][j]

    replace = dp[i+1][j+1]

    dp[i][j] = 1 + min(insert, delete, replace)

🧱 Base Cases

• If i == word1.length() → return remaining chars in word2 (need to insert all)

• If j == word2.length() → return remaining chars in word1 (need to delete all)

    class Solution {

    public int solve(int [][] dp,int i,int j,int n1,int n2,String word1, String word2)

    {

    if(i==n1)

    {

        return n2-j;

    }

    if(j==n2)

    {

        return n1-i;

    }

    if(dp[i][j] !=-1)

    {

        return dp[i][j];

    }

    if(word1.charAt(i)==word2.charAt(j))

    {

        dp[i][j]=solve(dp,i+1,j+1,n1,n2,word1,word2);

    }

    else

    {

        int insert=solve(dp,i,j+1,n1,n2,word1,word2);

        int delete=solve(dp,i+1,j,n1,n2,word1,word2);;

        int replace=solve(dp,i+1,j+1,n1,n2,word1,word2);

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

    }

    return dp[i][j];

    }

        public int minDistance(String word1, String word2) {

           

        int n1=word1.length();

        int n2=word2.length();

            int [][] dp=new int[n1][n2];

            for (int[] row : dp) {

                Arrays.fill(row, -1);

            }

            return solve(dp,0,0,n1,n2,word1,word2);

        }

    }