LeetCode : 72. Edit Distance

[congr]

https://leetcode.com/problems/edit-distance/description/

[congr]

Not easy at the first time,

https://en.wikipedia.org/wiki/Levenshtein_distance https://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/

https://leetcode.com/problems/edit-distance/discuss/25849/Java-DP-solution-O(nm)

f(i, j) := minimum cost (or steps) required to convert first i characters of word1 to first j characters of word2

Case 1: word1[i] == word2[j], i.e. the ith the jth character matches.

f(i, j) = f(i - 1, j - 1)

Case 2: word1[i] != word2[j], then we must either insert, delete or replace, whichever is cheaper

f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

f(i, j - 1) represents insert operation
f(i - 1, j) represents delete operation
f(i - 1, j - 1) represents replace operation

[congr]

LeetCode AC

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] D = new int [n+1][m+1];

        // init
        for (int i = 0; i <= n; i++) D[i][0] = i;
        for (int i = 0; i <= m; i++) D[0][i] = i;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1))
                    D[i][j] = D[i-1][j-1];
                else { // word1 modify
                    int insert = D[i][j-1];
                    int delete = D[i-1][j];
                    int replace = D[i-1][j-1];
                    D[i][j] = Math.min(Math.min(insert, delete), replace) + 1;
                }
            }
        }

        for (int i = 0; i <= n; i++) 
            System.out.println(Arrays.toString(D[i]));

        return D[n][m];
    }
}

[congr]

result is 3

[congr]

[congr]

InterviewBit AC - recursive "" "a" case fails

public class Solution {
    public int minDistance(String A, String B) {
        int N = A.length(), M = B.length();
        int[][] D = new int[N+1][M+1]; // !!!
        for (int i = 0; i<N; i++) Arrays.fill(D[i], -1);

        edit(A, N, B, M, D);

        for (int i = 0; i<N; i++) System.out.println(Arrays.toString(D[i]));
        return D[N][M];
    }

    int edit(String A, int a, String B, int b, int[][] D) {
        if (a == 0) return b;
        else if(b == 0) return a;
        if (D[a][b] > 0) return D[a][b];

        if (A.charAt(a-1) == B.charAt(b-1)) 
            D[a][b] = edit(A, a-1, B, b-1, D);
        else {
            int delete = edit(A, a-1, B, b, D); // delete A
            int insert = edit(A, a, B, b-1, D); // insert A 
            int replace = edit(A, a-1, B, b-1, D); // replace A
            D[a][b] = 1 + Math.min(Math.min(delete, insert), replace);
        }

        return D[a][b];
    } 
}

A : saturday, B : sunday result is 3

[congr]

LeetCode AC

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] d = new int[m+1][n+1];

        // don't return d[m][n], d[m][n] can have 0,
        // if the last letters are same.
        return edit(d, word1, word2, m, n); // !!! top-down
    }

    int edit(int[][] d, String a, String b, int u, int v) {
        if(u == 0) return v; // return a remaining count
        if(v == 0) return u;

        if (d[u][v] > 0) return d[u][v];

        if (a.charAt(u-1) == b.charAt(v-1))
            d[u][v] = edit(d, a, b, u-1, v-1);
        else {
            int insert = edit(d, a, b, u-1, v);
            int delete = edit(d, a, b, u, v-1);
            int replace = edit(d, a, b, u-1, v-1);
            d[u][v] = 1 + Math.min(insert, Math.min(delete, replace));
        }
        return d[u][v];
    }
}