Edit Distance leetcode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

dp[word1.length+1][word2.length+1]

state: dp[i][j]表示word1的前i个字符转换到word2的前j个字符最少的步骤数

function: if word1第i个字符和word2第j个字符相同: dp[i][j] = dp[i-1][j-1]// dp[i][j-1] = dp[i-1][j-1]+1 同理dp[i-1][j]

inital: dp[i][0] = i            dp[0][j] = j

return dp[word1.length][word2.length]//dp此时都返回dp[m][n]不是dp[m-1][n-1]
时间和空间都是O(m*n)

public class Solution {
    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 = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
//解法2 空间O（n）
public class Solution {
    public int minDistance(String word1, String word2) {
        int[] dp = new int[word1.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i] = i;
        }
        for (int j = 1; j <= word2.length(); j++) {
            int[] tem = new int[word1.length() + 1];
            tem[0] = j;
            for (int i = 1; i <= word1.length(); i++) {
                if (word1.charAt(i- 1) == word2.charAt(j - 1)) {
                    tem[i] = dp[i - 1];
                } else {
                    tem[i] = Math.min(tem[i - 1], Math.min(dp[i - 1], dp[i])) + 1;
                }
            }
            dp = tem;
        }
        return dp[word1.length()];
        
    }
}