题目：

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。 你可以对字符串进行3种操作：

1. 插入一个字符
2. 删除一个字符
3. 修改一个字符。

方法一：记忆化搜索

• 对于字符串str1和str2，如果str1为空，str2[0:j]不空，则可以将str2全部删除，操作次数为j,如果str1[0:i]不空，str2空，则可以在str2中插入和str1相同的字符，操作次数为i
• 如果str1和str2都不空，比较str[i]和str[j]，如果str[i]!=str[j]，则在替换删除和插入中选取最小值再增加一次操作次数,否则继承之前的值

由以上分析，可以采用递归的方法，用记忆化数组记录计算过的值，要得到memory[m][n]的值则只要进行递归计算，递归的终止条件为:i=0&&j==0,memory[i][j]=0

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int[][]memory;
    public int editDistance (String str1, String str2) {
        // write code here
         int m=str1.length(),n=str2.length();
         memory=new int[m+1][n+1];
         return dfs(str1,m,str2,n);
    }
    int dfs(String str1,int i,String str2,int j){
        if(memory[i][j]!=0)return memory[i][j];
        if(i==0&&j==0)return 0;
        //str1空，str2全部删除
        if(i==0&&j!=0){return memory[i][j]=dfs(str1,i,str2,j-1)+1;}
        //str2空，str1全部删除
        if(i!=0&&j==0){return memory[i][j]=dfs(str1,i-1,str2,j)+1;}
        //相等继承之前的值
        if(str1.charAt(i-1)==str2.charAt(j-1))return memory[i][j]=dfs(str1,i-1,str2,j-1);
        else//替换删除和插入中选最小值
            return memory[i][j]=Math.min(dfs(str1,i-1,str2,j-1),Math.min(dfs(str1,i,str2,j-1),dfs(str1,i-1,str2,j)))+1;
    }
}

function editDistance( str1 ,  str2 ) {
    // write code here
    const m=str1.length;
    const n=str2.length;
    let memory=new Array(m+1).fill(0).map(()=>Array(n+1).fill(0));
    return dfs(str1,m,str2,n,memory);
}
function dfs(str1,i,str2,j,memory){
    if(i==0&&j==0)return 0;
    if(i!=0&&j==0)return memory[i][j]=dfs(str1,i-1,str2,j,memory)+1;
    if(i==0&&j!=0)return memory[i][j]=dfs(str1,i,str2,j-1,memory)+1;
    if(memory[i][j]!=0)return memory[i][j];
    if(str1[i-1]==str2[j-1])return memory[i][j]=dfs(str1,i-1,str2,j-1,memory);
    else return memory[i][j]=Math.min(dfs(str1,i-1,str2,j-1,memory),Math.min(dfs(str1,i-1,str2,j,memory),dfs(str1,i,str2,j-1,memory)))+1
}
module.exports = {
    editDistance : editDistance
};

复杂度：

• 时间复杂度：$O(mn)O(mn)$
• 空间复杂度：$O(mn)O(mn)$,递归运行时栈和memory数组都占用空间

方法二：动态规划

记忆化搜索可以转化为动态规划，由方法一的分析，我们可以进行分析， 首先定义dp数组，dp[i][j]表示使得str1的前i个字符和str2的前j个字符相同的操作次数为dp[i][j] 然后，确定动态转移方程，

• $str1[i]==str2[j]str1[i]==str2[j]$,因为使得$str[0:i-1]==str[0:j-1]str[0:i-1]==str[0:j-1]$的操作次数为$dp[i-1][j-1],str1[i]==str2[j]=>dp[i][j]=dp[i-1][j-1]dp[i-1][j-1],str1[i]==str2[j]=>dp[i][j]=dp[i-1][j-1]$
• $str1[i]!=str2[j]str1[i]!=str2[j]$

1. 对str1进行删除操作，以下标i - 2为结尾的str1 与 j-1为结尾的str2的最近编辑距离 再加上一个操作，即$dp[i][j]=dp[i-1][j]+1dp[i][j]=dp[i-1][j]+1$
2. 对str2进行删除操作，以下标i-1结尾的str1与j-2结尾的str2的最近编辑距离再加上一个操作，即 $dp[i][j]=dp[i][j-1]+1dp[i][j]=dp[i][j-1]+1$;这里没有插入操作的原因是本质上插入操作的操作和删除操作的操作数一样，str2添加一个字符相当于str1删除一个字符，比如str1="ab",str2="a",此时将str2添加一个字符b变为“ab”的操作次数和str1删除一个字符变为"a"的操作次数相等。
3. 对str1或者str2进行替换操作，使得str[0:i-1]==str[0:j-1]的操作次数为dp[i-1][j-1]，因此要再加上一个操作，即$dp[i][j]=dp[i-1][j-1]+1dp[i][j]=dp[i-1][j-1]+1$ 在以上三种操作中选择最小值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
         int m=str1.length(),n=str2.length();
         int[][]dp=new int[m+1][n+1];
        for(int i=0;i<n+1;i++)dp[0][i]=i;//str[0,i]要转为空串需要删除操作i次
        for(int i=0;i<m+1;i++)dp[i][0]=i;
        
         for(int i=1;i<m+1;i++){
             for(int j=1;j<n+1;j++){
                 if(str1.charAt(i-1)==str2.charAt(j-1)){//如果字符相同，则继承为之前an的操作次数
                     dp[i][j]=dp[i-1][j-1];
                 }else{
                     dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;//替换为dp[i-1][j-1]+1,删除或插入为dp[i-1][j]+1或者dp[i][j-1]+1三者取最小
                 }
             }
         }
        return dp[m][n];
    }
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
 */
function editDistance( str1 ,  str2 ) {
    // write code here
    const m=str1.length;
    const n=str2.length;
    let dp=new Array(m+1).fill(0).map(()=>Array(n+1));
    for(let i=0;i<n+1;i++)dp[0][i]=i;
    for(let i=0;i<m+1;i++)dp[i][0]=i;
    for(let i=1;i<m+1;i++){
        for(let j=1;j<n+1;j++){
            if(str1[i-1]===str2[j-1])dp[i][j]=dp[i-1][j-1];
            else{
                dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
            }
        }
    }
    return dp[m][n];
    
}
module.exports = {
    editDistance : editDistance
};

复杂度：

• 时间复杂度：$O(mn)O(mn)$,双重循环
• 空间复杂度：$O(mn)O(mn)$，dp数组占用一定空间