Lintcode DP Edit Distance
18 Dec 2015###Task1 Example 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
Have you met this question in a real interview? Yes Example Given word1 = “mart” and word2 = “karma”, return 3.
###Java
public class Solution {
/**
* @param word1 & word2: Two string.
* @return: The minimum number of steps.
*/
public int minDistance(String word1, String word2) {
// write your code here
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n + 1][m + 1];
dp[0][0] = 0;
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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[n][m];
}
}
###point
- edit-distance-dynamic-programming if x == y, then dp[i][j] == dp[i-1][j-1] if x != y, and we insert y for word1, then dp[i][j] = dp[i][j-1] + 1 if x != y, and we delete x for word1, then dp[i][j] = dp[i-1][j] + 1 if x != y, and we replace x with y for word1, then dp[i][j] = dp[i-1][j-1] + 1 When x!=y, dp[i][j] is the min of the three situations.