Edit Distance

1package pkg5leetcode.official75;2 3/*4 * Edit Distance | LC 725 * APPROACH: 2D DP min ops insert/delete/replace.6 * COMPLEXITY: Time O(mn), Space O(mn)7 */8public class official75_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        return dp[m][n];21    }22 23    public static void main(String[] args) {24        check(minDistance("horse", "ros") == 3, "case1");25        check(minDistance("intention", "execution") == 5, "case2");26        System.out.println("all tests passed");27    }28 29    static void check(boolean cond, String name) {30        if (!cond) throw new AssertionError("FAILED: " + name);31        System.out.println("  PASS " + name);32    }33}