Edit Distance

1package pkg5leetcode.top100;2 3/*4 * Edit Distance | LC 725 * APPROACH: DP min edits insert/delete/replace between prefixes.6 * COMPLEXITY: Time O(m*n), Space O(m*n)7 */8public class top100_LC72EditDistance {9    static int minDistance(String word1, String word2) {10        int m = word1.length(), n = word2.length();11        int[][] dp = new int[m + 1][n + 1];12        for (int i = 0; i <= m; i++) dp[i][0] = i;13        for (int j = 0; j <= n; j++) dp[0][j] = j;14        for (int i = 1; i <= m; i++) {15            for (int j = 1; j <= n; j++) {16                if (word1.charAt(i - 1) == word2.charAt(j - 1))17                    dp[i][j] = dp[i - 1][j - 1];18                else19                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));20            }21        }22        return dp[m][n];23    }24 25    public static void main(String[] args) {26        check(minDistance("horse", "ros") == 3, "case1");27        check(minDistance("intention", "execution") == 5, "case2");28        System.out.println("all tests passed");29    }30 31    static void check(boolean cond, String name) {32        if (!cond) throw new AssertionError("FAILED: " + name);33        System.out.println("  PASS " + name);34    }35}