本文共 1462 字，大约阅读时间需要 4 分钟。

链接：

大意：

给定两个单词word1和word2，规定从word1转为word2的每个操作仅限于增加一次字符、删除一次字符或者修改一次字符。求word1转换为word2所需的最小转换次数。例子：

大意：

使用动态规划解决。详情见代码以及注释。

代码：

class Solution {    public int minDistance(String word1, String word2) {        int m = word1.length(), n = word2.length();                // cost数组含义： cost[i][j]:word1的前i个字符串转成word2的前j个字符串所需的最小操作次数        int[][] cost = new int[m + 1][n + 1];                // 初始化cost数组  如果word1=="" 则cost[0][j] = j        for (int j = 0; j <= n; j++)            cost[0][j] = j;                // 初始化cost数组  如果word2=="" 则cost[i][0] = i        for (int i = 0; i <= m; i++)            cost[i][0] = i;                // 动态规划  需要明白一点  当前你想得到的新状态是由之前的状态推得来的 而之前的状态对于现在的你 应该是知晓的        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                // 如果word1在i-1位置字符与word2在j-1位置字符一样 则不需要转换 即cost[i][j] = cost[i - 1][j - 1]                if (word1.charAt(i - 1) == word2.charAt(j - 1))                    cost[i][j] = cost[i - 1][j - 1];                // 否则依次查看对word1在i-1位置上的字符操作次数：增删改                else {                    int add = cost[i][j - 1] + 1; // 在word1的i-1位置上增加一个字符word2.charAt(j - 1)                    int delete = cost[i - 1][j] + 1; // 将word1在i-1的位置上的字符删掉                    int update = cost[i - 1][j - 1] + 1; // 将word1在i-1上的位置上的字符换成word2在j-1位置上的字符                    cost[i][j] = Math.min(Math.min(add, delete), update);                }            }        }        return cost[m][n];    }}

结果：

结论：

代码有优化空间。 

转载地址：http://laesi.baihongyu.com/