LintCode 119. Edit Distance 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/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
Example
Given word1 = "mart" and word2 = "karma", return 3.
解题思路
题目是求从word1变成word2的最小步骤数。
动态规划的代表题之一。动态规划方程f[i][j]表示从word1第i位置到word2第j位置的最小步骤数。
- 初始化，word1第i位置到word2第0位置需要i步骤（删除i次）。
- 初始化，word1第0位置到word2第j位置需要j步骤（插入j次）。
- 其他位置上，f[i][j]是word1第i – 1位置到word2第j位置 + 1（添加1次），word1第i位置到word2第j – 1位置 + 1（删除1次），word1第i – 1位置到word2第j – 1位置的最小值（word1第i – 1位置和word2第j – 1位置相等则就是f[i – 1][j – 1]，不相等则f[i – 1][j – 1] + 1(替换字母））。
参考代码
public class Solution {
/**
* @param word1 & word2: Two string.
* @return: The minimum number of steps.
*/
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] f = new int[m + 1][n + 1];
for (int i = 0; i < m + 1; i++) {
f[i][0] = i;
}
for (int j = 0; j < n + 1; j++) {
f[0][j] = j;
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
// insert, delete
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// no replace
f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
} else {
// replace
f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[m][n];
}
}