/** * Source : https://oj.leetcode.com/problems/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.) * * You have the following 3 operations permitted on a word: * * a) Insert a character * b) Delete a character * c) Replace a character */public class EditDistance {    /**     * 计算出从一个单词变到另一个单词的最少步数，也就是最短距离，只能使用插入、删除、替换操作     *     * 考虑两个单词abc,bbcd，dp[i][j]表示word1的前i个字符变到word2的前j个字符，所需要的步数，""表示空串     *    "" a b c     * "" 0  1 2 3     * b  1  1 1 2     * b  1  1 1 2     * c  3  3 2 1     * d  4  4 3 2     *     * 从上面的演算可以看出     * 当word1[i] == word2[j]的时候，dp[i][j] = dp[i-1][j-1]     * 当word1[i] != word2[j]的时候，dp[i][j] = 其左边、左上方、正上方三个数字中最小的那一个加1     *     *     * @param word1     * @param word2     * @return     */    public int minimumDistance (String word1, String word2) {        if (word1.length() == 0) {            return word2.length();        }        if (word2.length() == 0) {            return word1.length();        }        int[][] dp = new int[word1.length() + 1][word2.length() + 1];        for (int i = 0; i <= word1.length(); i++) {            dp[i][0] = i;        }        for (int i = 0; i <= word2.length(); i++) {            dp[0][i] = i;        }        for (int i = 1; i <= word1.length(); i++) {            for (int j = 1; j <= word2.length(); 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[word1.length()][word2.length()];    }    public static void main(String[] args) {        EditDistance editDistance = new EditDistance();        System.out.println(editDistance.minimumDistance("", "abc"));        System.out.println(editDistance.minimumDistance("b", "abc"));        System.out.println(editDistance.minimumDistance("bb", "abc"));        System.out.println(editDistance.minimumDistance("bbc", "abc"));        System.out.println(editDistance.minimumDistance("bbcd", "abc"));    }}