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
分析:本题用
动态规划的思想解答。用二维数组p[i][[j]表示word1[1...i]变为word2[1...j]需要经过最少的步数。若已知p[i][j]要p[i+1][j+1]对应3种操作,有三种转化方式
1. 修改一个字符。
当word1[i+1] != word2[j+1]时,需要修改字符,而word1[1…i]变换到word2[1...j]已经求得为p[i][j], 因此修改字符时,p[i+1][j+1] = p[i][j] + (word1[i+1] == word2[j+1]? 0:1)
2. 插入一个字符。
插入一个字符是在将word1[1...i+1]变换到word2[1...j]的基础上,插入一个字符使得word1[1...i+1]变换到word2[1....j+1],因此p[i+1][j+1] = p[i+1][j]+1;
3. 删除一个字符
需要删除时,说明字符word1[i+1]是多余的,删除后的字符串结果与将word1[1...i]变换到word2[1...j+1]相同,只是多了一步操作。因此p[i+1][j+1] = p[i][j+1]+1
p[i+1][j+1]取这三种变换的最小值。
所以
p[i][j] = min(p[i-1][j-1] +(word1[i] == word2[j] ? 0 :1), min(p[i][j-1] +1, p[i-1][j] +1) )
初始化:
p[0][j] 表示将空字符串转化成word2[1...j],因此 p[0][j] = j
p[i][0] 表示将word1[1…i]转化成空字符串,因此p[i][0] = i
算法复杂度O(mn)
代码:
public class Edit_Distance {
public int minDistance(String word1, String word2) {
int p[][] = new int[word1.length()+1][word2.length()+1];
for(int i=0;i<p[0].length;++i)
p[0][i] = i;
for(int i=0;i<p.length;++i)
p[i][0] = i;
for(int i=1;i<=word1.length();++i){
for(int j=1;j<=word2.length();++j){
p[i][j] = Math.min(p[i][j-1]+1, Math.min(p[i-1][j]+1, p[i-1][j-1]+(word1.charAt(i-1)== word2.charAt(j-1)? 0: 1)));
}
}
return p[word1.length()][word2.length()];
}
}
分享到:
相关推荐
LeetCode题解(java语言实现).pdf
LeetCode book——CleanCodeHandbook_v1.0.1
leetcode题解 算法和数据结构题目及解答
Leetcode 题解.pdf
分享 技术面试必备基础知识、Leetcode 题解、Java、C++、Python、后端面试、操作系统、计算机网络、系统设计分享 技术面试必备基础知识、Leetcode 题解、Java、C++、Python、后端面试、操作系统、计算机网络、系统...
c++ c++_c++编程基础之leetcode题解第37题解数独
LeetCode题解 - Java语言实现-181页.pdf
LeetCode题解(java语言实现)
c语言 c语言_c语言编程基础之leetcode题解第7题整数反转
1. 给表达式加括号 2. 不同的二叉搜索树 1. 给表达式加括号 2. 不同的二叉搜索树
500195422331430LeetCode题解 - Java语言实现.zip
c语言 c语言_c语言编程基础之leetcode题解第8题字符串转整数
基于Java和TypeScript的数据结构,LeetCode题解
Leetcode 5个经典元素和问题题解。
c++ c++_c++编程基础之leetcode题解第66题加一
c++ c++_c++编程基础之leetcode题解第77题组合
c++ c++_c++编程基础之leetcode题解第78题子集
c++ c++_c++编程基础之leetcode题解第46题全排列
c++ c++_c++编程基础之leetcode题解第54螺旋矩阵
c语言 c语言_c语言编程基础之leetcode题解第9题回文数