Created
December 30, 2017 21:24
-
-
Save jianminchen/8cd9b47a458ca288525d871796d66b74 to your computer and use it in GitHub Desktop.
Leetcode 72 - edit distance - study the code and give some code review
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package DP; | |
import java.util.Arrays; | |
/** | |
Dec. 30, 2017 Study the blog: | |
http://blog.csdn.net/fightforyourdream/article/details/13169573 | |
* 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 | |
*/ | |
public class EditDistance { | |
static int[][] dist = null; | |
public static void main(String[] args) { | |
String word1 = "sdfsssjdfhsb"; | |
String word2 = "cvdsfadfgkdfgj"; | |
dist = new int[word1.length()+1][word2.length()+1]; | |
for(int[] row : dist){ | |
Arrays.fill(row, -1); | |
} | |
System.out.println(minDistance(word1, word2)); | |
System.out.println(minDistance2(word1, word2)); | |
} | |
public static int min3(int a, int b, int c){ | |
return Math.min(Math.min(a, b), c); | |
} | |
// DP bottom-up | |
public static int minDistance(String word1, String word2) { | |
int[][] distance = new int[word1.length()+1][word2.length()+1]; | |
// 边界情况:当其中一个string为空时,只要一直添加或删除就可以 | |
for(int i=0; i<=word1.length(); i++){ | |
distance[i][0] = i; | |
} | |
for(int j=1; j<=word2.length(); j++){ | |
distance[0][j] = j; | |
} | |
// 递推,[i][j]处可以由左,上,左上3种情况而来 | |
for(int i=1; i<=word1.length(); i++){ | |
for(int j=1; j<=word2.length(); j++){ | |
distance[i][j] = min3(distance[i-1][j]+1, // 从上演变 | |
distance[i][j-1]+1, // 从左演变 | |
distance[i-1][j-1]+(word1.charAt(i-1)==word2.charAt(j-1) ? 0 : 1)); | |
// 从左上演变,考虑是否需要替换 | |
} | |
} | |
return distance[word1.length()][word2.length()]; // 返回右下角 | |
} | |
// 递归,太慢 | |
public static int minDistance2(String word1, String word2) { | |
// return rec(word1, word1.length(), word2, word2.length()); | |
return rec2(word1, word1.length(), word2, word2.length()); | |
} | |
public static int rec(String word1, int len1, String word2, int len2){ | |
if(len1 == 0){ | |
return len2; | |
} | |
if(len2 == 0){ | |
return len1; | |
} | |
if(word1.charAt(len1-1) == word2.charAt(len2-1)){ | |
return rec(word1, len1-1, word2, len2-1); | |
}else{ | |
return min3(rec(word1, len1-1, word2, len2-1) + 1, | |
rec(word1, len1, word2, len2-1) + 1, | |
rec(word1, len1-1, word2, len2) + 1); | |
} | |
} | |
// 添加全局数组,保存状态,用空间换时间 DP top-down | |
public static int rec2(String word1, int len1, String word2, int len2){ | |
if(len1 == 0){ | |
return len2; | |
} | |
if(len2 == 0){ | |
return len1; | |
} | |
if(word1.charAt(len1-1) == word2.charAt(len2-1)){ | |
if(dist[len1-1][len2-1] == -1){ | |
dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1); | |
} | |
return dist[len1-1][len2-1]; | |
}else{ | |
if(dist[len1-1][len2-1] == -1){ | |
dist[len1-1][len2-1] = rec2(word1, len1-1, word2, len2-1); | |
} | |
if(dist[len1][len2-1] == -1){ | |
dist[len1][len2-1] = rec2(word1, len1, word2, len2-1); | |
} | |
if(dist[len1-1][len2] == -1){ | |
dist[len1-1][len2] = rec2(word1, len1-1, word2, len2); | |
} | |
dist[len1][len2] = min3(dist[len1-1][len2-1]+1, dist[len1][len2-1]+1, dist[len1-1][len2]+1); | |
return dist[len1][len2]; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment