代码随想录Day59

72.编辑距离

题目：72. 编辑距离 - 力扣（LeetCode）

思路：就这跟编辑距离有啥关系，跟最长公共子序列肯定是有关系的

dp数组定义：

dp[i][j]表示，包含i-1在内的word1转换为包含j-1下标在内的word2所需的最少操作数

递推公式：

char[i-1]==char[j-1]时，dp[i][j] = dp[i-1][j]

dp[i-1][j] + 1

尝试（瞎写的）

class Solution {
    public int minDistance(String word1, String word2) {
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i<word2.length(); i++){
            dp[0][i] = i;
        }
        for(int i = 1; i<=word1.length(); i++){
            for(int j = 1; j<= word2.length(); j++){
                if(char1[i-1]==char2[j-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j]+1;
                }
            }
        }
        return dp[word1.length()][word2.length()]-1;
    }
}

答案

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // 初始化
    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++) {
            // 因为dp数组有效位从1开始
            // 所以当前遍历到的字符串的位置为i-1 | j-1
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
    }
    return dp[m][n];
}

小结

定义没错，初始化对了，但是递推公式不会

题目中说的是操作word1使得它变成word2，实际上操作word2变成word1跟这个次数是一样的，甚至可以同时操作两个字符串，使其变成同一个单词