新博文地址:[leetcode]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
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
这道题在编程之美上有原题,书中给出的答案是用 递归版实现,代码如下:
public int minDistanceWithRecurse(String word1, String word2) { if(word1.length() == 0){ return word2.length(); } if(word2.length() == 0){ return word1.length(); } if(word1.charAt(0) == word2.charAt(0)){ return minDistance(word1.substring(1), word2.substring(1)); }else{ int t1 = minDistance(word1.substring(1), word2); int t2 = minDistance(word1, word2.substring(1)); int t3 = minDistance(word1.substring(1), word2.substring(1)); return Math.min(t1, Math.min(t2, t3)) + 1; } }
但是坑爹的超时了,后来想了一下,还是不会,google之,发现原来Edit Distance是自然语言处理中的很重要的一个算法,而且自成一脉。大家可以去看下维奇百科的解释,Edit Distance中明确的说明了这个问题用递归实现的复杂度是指数级的,因此,采用了DP解决思路:百科中已经讲得很明白了。这里就简单的小结一下:
维护一个二维矩阵来记录distance的状态:
dinstance[i][j]分别表示字符串word1[0~i]与word2[0~j]的距离
这里需要将distance开到[word1.length() +1][word2.length() + 1]
dinstance[i][j]分别表示字符串word1[0~i]与word2[0~j]的距离
这里需要将distance开到[word1.length() +1][word2.length() + 1]
其中[0][0]表示二者都为空串时,distance显然为0.
当i = 0时,distance[0][j] = j (其中 1 <= j <= word2.length()),同理
当j = 0时,distance[i][0] = i (其中 1 <= i <= word1.length())
当i = 0时,distance[0][j] = j (其中 1 <= j <= word2.length()),同理
当j = 0时,distance[i][0] = i (其中 1 <= i <= word1.length())
而distance[i][j]有两种情况
当word1.charAt(i) == word2.charAt(j)时,
显然distance[i][j] = distance[i-1][j - 1];
当word1.charAt(i) != word2.charAt(j)时,
需要考察distance[i - 1][j - 1]、 distance[i][j - 1]、distance[i - 1][j]分别对应了三种情况:修改word1[i] 为word2[j]、删除word2[j]、删除word1[i],找到这三者中最小的一个数 ,然后+ 1(表示删除操作或者修改操作)
当word1.charAt(i) == word2.charAt(j)时,
显然distance[i][j] = distance[i-1][j - 1];
当word1.charAt(i) != word2.charAt(j)时,
需要考察distance[i - 1][j - 1]、 distance[i][j - 1]、distance[i - 1][j]分别对应了三种情况:修改word1[i] 为word2[j]、删除word2[j]、删除word1[i],找到这三者中最小的一个数 ,然后+ 1(表示删除操作或者修改操作)
具体的还需要看这里:
代码如下:
public int minDistance(String word1, String word2) { int length1 = word1.length(); int length2 = word2.length(); if(length1 == 0 || length2 == 0){ return length1 == 0? length2: length1; } int[][] distance = new int[length1 + 1][length2 + 1]; distance[0][0] = 0; for(int i = 1; i <= length1; i++){ distance[i][0] = i ; } for(int i = 1; i <= length2; i++){ distance[0][i] = i ; } for(int i = 1; i <= length1; i++){ for(int j = 1; j <= length2; j++){ if(word1.charAt(i-1) == word2.charAt(j-1)){ distance[i][j] = distance[i - 1][j - 1]; }else{ distance[i][j] = Math.min(distance[i - 1][j - 1], Math.min(distance[i][j - 1], distance[i - 1][j])) + 1; } } } return distance[length1][length2]; }
相关推荐
idea leetcode插件 安装方法选择install plugn from disk
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode编辑器leetcode-问题 自定义代码演示 leetcode 编辑器配置 代码文件名: $ ! velocityTool . camelCaseName(${question . titleSlug}) 代码模板: ${question . content} package ...
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记
LeetCode 刷题
(C++)LeetCode刷题题解答案