首页 > 代码库 > LintCode刷题笔记-- Edit distance
LintCode刷题笔记-- 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:
- Insert a character
- Delete a character
- Replace a character
解题思路：
这一题做的很快，与之前的字符串匹配问题一样，在word1与word2的两个向量上分解字符串，同时遍历两个字符串：分别在两个子串中进行比较，
对于子串中拥有相同的字符的情况下：加入这个字符与不加入这个字符的意义是相同的，不会有更多的变化，所以有公式：
dp[i][j] = dp[i-1][j-1]
当两个子串的匹配的字符不同的情况下：有三种情况可以达到当前状态，修改1位，删除1位，加入1位，三个分别的位置为dp[i-1][j], dp[i][j-1],dp[i-1][j-1]
且三个位置记录着之前状态下，所存在的最小变化情况。所以要在当前状态下达到最小，则需要在之前最小的情况下加上1，所以公式有：
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
参考代码：
public int minDistance(String word1, String word2) { // write your code here int[][] dp = new int[word1.length()+1][word2.length()+1]; for(int i = 0; i<=word1.length(); i++){ dp[i][0] = i; } for(int j = 0; j<=word2.length(); j++){ dp[0][j] = j; } 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(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1; } } } return dp[word1.length()][word2.length()]; }
LintCode刷题笔记-- Edit distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。