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


&nbsp;
Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -&gt; rorse (replace 'h' with 'r')
rorse -&gt; rose (remove 'r')
rose -&gt; ros (remove 'e')


Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -&gt; inention (remove 't')
inention -&gt; enention (replace 'i' with 'e')
enention -&gt; exention (replace 'n' with 'x')
exention -&gt; exection (replace 'n' with 'c')
exection -&gt; execution (insert 'u')


&nbsp;
Constraints:


	0 &lt;= word1.length, word2.length &lt;= 500
	word1 and word2 consist of lowercase English letters.


from functools import cache


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        
        @cache
        def dp(i, j):
            if i == 0:
                return j
            if j == 0:
                return i
            
            l1, l2 = word1[i - 1], word2[j - 1]
            if l1 != l2:
                return 1 + min(
                    dp(i, j - 1),     # Delete / insert j
                    dp(i - 1, j),     # Delete / insert i
                    dp(i - 1, j - 1)  # Replace i or j
                )
            return dp(i - 1, j - 1)         
                    
        return dp(m, n)
class Solution {
    
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int dp[][] = new int[m][n];
        for(int i=0 ; i<m ; i++){
            for(int j=0 ; j<n ; j++){
                dp[i][j] = -1;
            }
        }
        return solve(word1, word2 , m-1, n-1 ,dp);
    }
    
    public int solve(String str1, String str2, int m , int  n , int dp[][]){
        if(m<0){
            return n+1;
        }
        if(n<0){
            return m+1;
        }
        if(dp[m][n] != -1){
            return dp[m][n];
        }
        if(str1.charAt(m) == str2.charAt(n)){
            return solve(str1, str2 , m-1, n-1 ,dp);
        }
        else{
            int min = Math.min(solve(str1, str2, m-1 ,n ,dp), solve(str1, str2, m ,n-1 , dp));
            dp[m][n] = 1+Math.min(min, solve(str1, str2, m-1, n-1, dp));
        }
        return dp[m][n];
    }
}
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};
var minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;

    const memo = new Array(m).fill().map(() => new Array(n));
    const dfs = (i = m - 1, j = n - 1) => {
        if(i < 0 && j < 0) return 0;
        if(i < 0 && j >= 0) return j + 1;
        if(i >= 0 && j < 0) return i + 1;
        if(memo[i][j] !== undefined) return memo[i][j];

        if(word1[i] === word2[j]) {
            return memo[i][j] = dfs(i - 1, j - 1);
        }

        return memo[i][j] = 1 + Math.min(...[
            dfs(i, j - 1),
            dfs(i - 1, j),
            dfs(i - 1, j - 1)
        ]);
    }

    return dfs();
};
Edit Distance