【动态规划】72. 编辑距离

72. 编辑距离

解题思路

• dp(i,j)表示当前两个字符串指针i,j处所需要的最小编辑距离
• 如果s1[i]== s2[j] 那么不需要编辑 直接移动到dp(i - 1,j - 1)
• 如果当前两个指针指向的字符不相等，判断删除，插入，替换三种操作的最小值

class Solution {

    int[][] memo;// 添加备忘录

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

        memo = new int[m][n];

        // 全部初始化-1
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }

        return dp(word1,word2,m - 1,n - 1);
    }

    int dp(String s1,String s2,int i,int j){
        if(i == -1){
            // 说明s1已经走完  直接将s2的剩余部分 插入s1
            // 最小编辑距离就是 j + 1
            return j + 1;
        }

        if(j == -1){
            // 说明s2已经走完 将s1剩余部分直接删除
            // 最小编辑距离就是 i + 1
            return i + 1;
        }

        if(memo[i][j] != -1){
            return memo[i][j];
        }

        // 当前两个字符相等 不需要编辑 编辑距离 取决于(i - 1,j - 1)
        if(s1.charAt(i) == s2.charAt(j)){
            memo[i][j] = dp(s1,s2,i - 1,j - 1);// 两个指针同时向下移动
        }else{
             // 插入  删除  替换
        memo[i][j] =  Math.min(
            dp(s1,s2,i,j - 1) + 1,
            Math.min(dp(s1,s2,i - 1,j) + 1,
            dp(s1,s2,i - 1,j - 1) + 1)
        );
        }

        // dp(s1,s2,i,j - 1) + 1  插入操作 直接在i出插入一个和s[j]一样的字符  移动j 继续和i比较

        return memo[i][j];
    }
}