编辑距离(一)

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        int s1Len = str1.length();
        int s2Len = str2.length();
        // 如果有一个字符串长度等于0，那么最小变换次数即为 s1Len + s2Len;
        if(s1Len == 0 || s2Len == 0) return s1Len + s2Len;
        

        // 初始化dp数组，dp[i][j] 记录 str1 每一个字符 变成 str2的次数
        int[][] dp = new int[s1Len + 1][s2Len + 1]; // 第一行第一列，辅助单元格
        // 初始化第一行
        // 可以理解为: 将一个空串，转变为str2字符串从0 ~ i的字符 所需要的次数
        for (int i = 1; i < dp[0].length; i++) dp[0][i] = i;
        // 初始化第一列
        // 可以理解为: 将str1字符串从0 ~ i的字符 转变为 一个空串 所需要的次数
        for (int i = 1; i < dp.length; i++) dp[i][0] = i;

        // 下标从1开始遍历每一行
        for (int i = 1; i < dp.length; i++) {
            // 取出str1的 i索引字符
            char strChar1 = str1.charAt(i - 1);
            // 下标从1开始遍历每一列
            for (int j = 1; j < dp[0].length; j++) {
                // 取出str2的 j索引字符
                char strChar2 = str2.charAt(j - 1);
                // 如果相等，那么只需要取出左斜方单元格记录的次数即可
                if(strChar1 == strChar2){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    // 如果不相等，取出左斜方，上方，左方的值，取最小后 + 1 即为当前 0 ~ i索引的str1字符串变换成 0 ~ j索引的str2字符串所需要的次数
                    int i1 = dp[i - 1][j - 1];
                    int i2 = dp[i][j - 1];
                    int i3 = dp[i-1][j];
                    dp[i][j] = Math.min(i3, Math.min(i1, i2)) + 1;
                }
            }
        }

        // 循环结束，dp表格最后一个单元格记录的值，即为解
        return dp[s1Len][s2Len];
    }
}

import java.util.*;


public class Solution {
    private int arr[][];
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        String longOne = str1, shortOne = str2;

        arr = new int[longOne.length()][shortOne.length()];
        for (int i =0;i<longOne.length();i++) {
            for (int j =0;j<shortOne.length();j++) {
                arr[i][j] = 0;
            }
        }

        return searchDistance(longOne, shortOne, 0, 0);
    }
    
    public int searchDistance(String longOne, String shortOne, int longIndex, int shortIndex) {
        if (longOne.length() <= longIndex) {
            return shortOne.length() - shortIndex > 0 ? shortOne.length() - shortIndex:0;
        } else if (shortOne.length() <= shortIndex) {
            return longOne.length() - longIndex > 0 ? longOne.length() - longIndex: 0;
        }
        
        if(arr[longIndex][shortIndex] != 0) {
            return arr[longIndex][shortIndex];
        }
        if (shortOne.charAt(shortIndex) == longOne.charAt(longIndex)) {
            arr[longIndex][shortIndex] = searchDistance(longOne, shortOne, longIndex + 1, shortIndex + 1);
            return arr[longIndex][shortIndex];
        } else {
            int d1 = searchDistance(longOne, shortOne, longIndex + 1, shortIndex + 1);
            int d2 = searchDistance(longOne, shortOne, longIndex, shortIndex + 1);
            int d3 = searchDistance(longOne, shortOne, longIndex + 1, shortIndex );
            
            arr[longIndex][shortIndex] = 1 + Math.min(d1, Math.min(d2,d3));
            return arr[longIndex][shortIndex];
        }
    }
}

import java.util.*;

public class Solution {
    int[][] memo; //备忘录，记录递归中间结果
    public int editDistance (String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        memo = new int[len1][len2];
        //初始化备忘录
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        //用二个指针从二个字符串末尾开始向前遍历
        return dp(word1, word2, len1- 1, len2 - 1);
    }
     //dp(i,j)表示以i的字符串s1变为以j结尾的s2的最少操作数
    int dp(String s1, String s2, int i, int j) {
        //如果s1遍历结束，则s1添加s2的剩余字符
        if (i == -1) return j + 1;
        //如果s2遍历结束，则s1删掉s2的剩余字符
        if (j == -1) return i + 1;

        //如果计算过则直接返回
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        //如果当前位置相等，则什么都不做
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, s2, i - 1, j - 1);
        } else { //如果不等，则进行增、删、换
            //增加：i比不变，j前移。删除：i前移，j不变
            int temp = Math.min(dp(s1, s2, i, j - 1), dp(s1, s2, i - 1, j)) + 1;
            //替换；i和j都前移
            memo[i][j] = Math.min(temp, dp(s1, s2, i - 1, j - 1) + 1);
        }
        return memo[i][j];
    }
}

    public int editDistance(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int len1 = s1.length;
        int len2 = s2.length;
        // 定义dp[i][j]为字符串1和2分别到i,j位置时的编辑距离
        int[][] dp = new int[len1 + 1][len2 + 1];
        // base case 如果其中一个为空，操作数为另一个的长度
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            dp[0][j] = j;
        }
        /*
         * 动态转移方程:
         * 如果char[i-1] = char[j-1] 字符相等 那么 dp[i][j] = dp[i-1][j-1];
         * 否则就是 增加 删除 替换 中较小的那个 dp[i][j-1] dp[i-1][j] dp[i-1][j-1] + 1;
         *
         */
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

java版——动态规划
dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的编辑距离。

(以下说的相等是指我们已经知道它们的编辑距离)

• 如果 str1 的前 i - 1 个字符和 str2 的前 j 个字符相等，那么我们只需要在 str1 最后插入一个字符就可以转化为 str2 。 dp[i][j] = dp[i - 1][j] + 1
• 如果 str1 的前 i 个字符和 str2 的前 j - 1 个字符相等，那么我们只需要在 str1 最后删除一个字符就可以转化为 str2 。 dp[i][j] = dp[i][j - 1] + 1
• 如果 str1 的前 i - 1 个字符和 str2 的前 j - 1 个字符相等，那么我们要判断 str1 和 str2 最后一个字符是否相等：
  • 如果相等，则不需要任何操作。 dp[i][j] = dp[i - 1][j - 1]
  • 如果不相等，则只需要将 str1 最后一个字符修改为 str2 最后一个字符即可。dp[i][j] = dp[i - 1][j - 1] + 1

最终 dp[i][j] 为上面三种状态的最小值：
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

奥，对了，我们还要考虑边界情况，当str1为空时，编辑距离就为str2的长度（str1依次插入str2个字符），当str2为空时编辑距离就为str1的长度（str1依次删除每个字符）。

import java.util.*;

public class Solution {

    public int editDistance (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        if(len1 == 0 || len2 == 0){
            return len1 + len2;
        }
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(str1.charAt(i - 1) == str2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
}

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        //str1前i个字符转换到str2前j个字符的最少操作数
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        //如果后字符串全为空，则全删除
        for(int i=0; i<=str1.length(); i++){
            dp[i][0] = i;
        }
        //如果前字符串全为空，则全添加
        for(int j=0; j<=str2.length(); j++){
            dp[0][j] = j;
        }
        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] =  dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}