Edit Distance
Edit Distance (leetcodelintcode)
Description
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.
解题思路
动态规划，本题与 LCS 类似。
- 定义状态：定义
f[i][j]为字符串A的前i个字符 匹配 字符串B的前j个字符需要执行的最少操作数量 。 - 定义状态转移函数：对于当前状态
f[i][j]，由于涉及操作较多，所以需要详细讨论：A[i - 1] == B[j - 1]时。- 无操作
：上一个状态可能是
f[i - 1][j - 1]，此时无需任何操作。- 插入操作
：如果需要对
A末尾执行一次插入操作，插入之后A[i] == B[j - 1]，那么执行操作前A的前i个字符和B的前j - 1个字符相匹配，上一个状态是f[i][j - 1]。 - 删除操作
：如果需要对
A末尾执行一次删除操作，删除之后A[i - 2] == B[j - 1]，那么执行操作前A的前i - 1个字符和B的前j个字符相匹配，上一个状态是f[i - 1][j]。 - 综上， 当前状态需要取以上三种情况的最小值。
- 插入操作
：如果需要对
A[i - 1] != B[j - 1]时。- 替换操作
：将
A的第i个字符替换为B的前j个字符，那么执行操作前A的前i - 1个字符和B的前j - 1个字符相匹配，上一个状态是f[i - 1][j - 1]。 - 插入操作
：如果需要对
A末尾执行一次插入操作，插入之后A[i] == B[j - 1]，那么执行操作前A的前i个字符和B的前j - 1个字符相匹配，上一个状态是f[i][j - 1]。 - 删除操作
：如果需要对
A末尾执行一次删除操作，删除之后A[i - 2] == B[j - 1]，那么执行操作前A的前i - 1个字符和B的前j个字符相匹配，上一个状态是f[i - 1][j]。 - 综上，当前状态需要取以上三种情况的最小值。
- 替换操作
：将
- 定义起点：起点
f[0][0] == 0，当A为空或B为空时，对应的状态函数f[0][j]或f[i][0]，从起点出发分别需要j或i次操作。 - 定义终点：最终结果即为
f[n][m]。
易错点：
- 在处理边界情况时，如果其中一个字符串长度为 0，程序时可以处理的，所以只要考虑字符串为空的情况即可。
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
if
(word1 ==
null
|| word2 ==
null
) {
return
0
;
}
int
n = word1.length();
int
m = word2.length();
// state
int
[][] f =
new
int
[n +
1
][m +
1
];
// initialize
for
(
int
i =
0
; i
<
= n; i++) {
f[i][
0
] = i;
}
for
(
int
j =
1
; j
<
= m; j++) {
f[
0
][j] = j;
}
// top down
for
(
int
i =
1
; i
<
= n; i++) {
for
(
int
j =
1
; j
<
= m; j++) {
if
(word1.charAt(i -
1
) == word2.charAt(j -
1
)) {
f[i][j] = Math.min(f[i -
1
][j -
1
],
Math.min(f[i][j -
1
] +
1
, f[i -
1
][j] +
1
));
}
else
{
f[i][j] = Math.min(f[i -
1
][j -
1
],
Math.min(f[i -
1
][j], f[i][j -
1
]))
+
1
;
}
}
}
// end
return
f[n][m];
}
}
优化空间（滚动数组）：
观察状态转移函数，f[i][j]由f[i - 1][j]或f[i][j - 1]决定，与前i - 2行无关，所以可利用滚动数组进行优化。
public
class
Solution
{
/**
*
@param
word1
&
word2: Two string.
*
@return
: The minimum number of steps.
*/
public
int
minDistance
(String w1, String w2)
{
if
(w1 ==
null
|| w2 ==
null
) {
return
0
;
}
int
m = w1.length();
int
n = w2.length();
// status
int
[][] f =
new
int
[
2
][n +
1
];
// initialize
for
(
int
i =
0
; i
<
= n; i++) {
f[
0
][i] = i;
}
for
(
int
i =
1
; i
<
= m; i++) {
f[i %
2
][
0
] = i;
for
(
int
j =
1
; j
<
= n; j++) {
if
(w1.charAt(i -
1
) == w2.charAt(j -
1
)) {
f[i %
2
][j] = Math.min(f[(i -
1
) %
2
][j -
1
], Math.min(f[(i -
1
) %
2
][j], f[i %
2
][j -
1
]) +
1
);
}
else
{
f[i %
2
][j] = Math.min(f[(i -
1
) %
2
][j -
1
], Math.min(f[(i -
1
) %
2
][j], f[i %
2
][j -
1
])) +
1
;
}
}
}
return
f[m %
2
][n];
}
}