Edit Distance

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.)

• Time: O(n * m)
• Space: O(n * m)

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 1; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (word1.charAt(i) == word2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j];
            } else {
                dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1]
                                   , dp[i + 1][j]), dp[i][j]) + 1;
            }
        }
    }
    return dp[m][n];
}