频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
LeetCode 72题目解答
2017-04-21 09:45:18           
收藏   我要投稿

LeetCode 72题目解答:将字符串word1编辑成word2的操作步数,最小的操作步数称为edit distance(编辑距离),有三种操作:插入,删除,替换。

利用动态规划DP解决,建立距离矩阵,工作的就是填矩阵,时间复杂度O(mn),mn是字符串的长度。

dist[i][j]可能由三种状态转移得到:

// j = indexof word1    i = indexof word2

dist[i-1][j-1] -> dist[i][j]
如果word1[j-1] == word2[i-1] 那么直接得到,否则需要替换操作
dist[i-1][j] -> dist[i][j]
插入操作
dist[i][j-1] -> dist[i][j]
删除操作

算法开始,需要对第一行及第一列赋初值,初值代表插入删除操作直接得到word2
之后定义cost代表word1和word2对应位置的字符是否想等,相等则cost为0,又dist[i-1][j-1] -> dist[i][j] 只是新增了一个相同的字符,不需要进一步操作。
比较三个值,dist[i-1][j]+1 dist[i][j-1]+1 dist[i-1][j-1]+cost,较小者为编辑距离。得到的矩阵dist[i][j]值就是word1[1…j]编辑成word2[1….i]所需要的编辑距离。

public class Solution {
    public int minDistance(String word1, String word2) {
        //word1编辑成word2的编辑距离
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dist = new int[len2+1][len1+1];
        //第一列赋值为0
        for(int i = 0;i <= len2;i ++)
        {
            dist[i][0] = i;
        }
        for(int j = 0;j <= len1;j ++)
        {
            dist[0][j] = j;
        }
        int cost;
        for(int i = 1;i <= len2;i ++)
            for(int j = 1;j <= len1;j ++)
            {
                if(word1.charAt(j-1) == word2.charAt(i-1))
                    cost = 0;
                else cost = 1;
                dist[i][j] = Math.min(dist[i-1][j-1]+cost,Math.min(dist[i-1][j]+1,dist[i][j-1]+1));
            }
        return dist[len2][len1];
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:有向图的无权图最短路径算法与带权图的Dijkstra算法
下一篇:SpringBoot+Mybatis显示sql
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站