一、题目描述
编辑距离(edit distance)— 我们把两个字符串的相似度定义为:将一个字符串转换成另外一个字符串时需要付出的代价。转换可以采用插入、删除和替换三种编辑方式，因此转换的代价就是对字符串的编辑次数。而编辑距离就是从一个字符串到另一个字符串的最少编辑次数。
示例：
以字符串“SNOWY”和“SUNNY”为例，下面是两种将“SNOWY”转换为“SUNNY”的方法
-
转换方法1：
S - N O W Y S U N N - Y- 1
- 2
转换代价Cost = 3 (插入U、替换O、删除W)
-
转换方法2：
- S N O W - Y S U N - - N Y- 1
- 2
转换代价Cost = 5 (插入S、替换S、删除O、删除W、插入N)。
不同的转换方法需要的编辑次数也不一样，最少的那个编辑次数就是字符串的编辑距离。
二、解题思路
设字符串P为模式串，T为文本串。在模式串P进行编辑成为T。
1. 定义状态
设dp[i][j]为P1,P2,…,Pi和结束于j的T的某个前缀片段之间文本差异的最小值。换言之，dp[i][j]是一下三种能给出较短字符串方式所花费用的最小值：
- 若Pi = Tj,则为dp[i-1][j-1]，反之则为dp[i-1][j-1] + 1。这意味着，要么第i个字符和第j个字符匹配，要么我们得用Tj替换Pj。这取决于这两个尾部字符是否相同。
- dp[i][j-1]。意味着文本中多一个字符，因此我们需要前移文本串的位置指针，但得为模式串插入操作支付一次费用。
- dp[i-1][j]。这意味着模式中多了一个字符，得删除它，因此我们需要前移模式串的位置指针，但得为删除操作支出一次费用。
2. 定义状态转移方程
当 P[i] = T[k]时，有
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j] = dp[i-1][j-1] dp[i][j]=dp[i−1][j−1]
否则：
d
p
[
i
]
[
j
]
=
m
a
x
{
d
p
[
i
−
1
]
[
j
−
1
]
+
1
d
p
[
i
−
1
]
[
j
]
+
1
d
p
[
i
]
[
j
−
1
]
+
1
dp[i][j] = max
3. 初始化
dp[0][j] 初始化为j。
dp[i][0] 初始化为i。
三、代码实现
/**
* 字符串最小编辑距离
*
* @author hh
*/
public class MinEditDistance {
/**
* 求字符串p和字符串t的最小编辑距离
*
* @param p 模式串
* @param t 文本串
* @return 最小编辑距离
*/
public int minDistance(String p,String t){
int[][] dp = new int[p.length() + 1][t.length() +1];
//初始化行
for(int i = 0 ; i <= t.length(); i++ ){
dp[0][i] = i;
}
//初始化列
for(int i = 0; i <= p.length(); i++){
dp[i][0] = i;
}
for(int i = 1; i <= p.length(); i++){
for(int j = 1; j <= t.length(); j++){
dp[i][j] = Integer.MAX_VALUE;
if (p.charAt(i - 1) == t.charAt(j -1)) {
dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]);
}else{
dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1] + 1);
}
//和删除比较
dp[i][j] = Math.min(dp[i][j],dp[i-1][j] + 1);
//和插入比较
dp[i][j] = Math.min(dp[i][j],dp[i][j-1] + 1);
}
}
return dp[p.length()][t.length()];
}
public static void main(String[] args){
String p = "steve"; // "thou-shalt-not";
String t = "setve"; // "you-should-not";
MinEditDistance minEditDistance = new MinEditDistance();
System.out.println(minEditDistance.minDistance(p,t));
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
四、执行结果
五、拓展
我们在打字时经常会犯换位错误(交换了相邻的字符),例如你想录入“steve"却打成了“setve".在编辑距离的常规定义体系下，换位需要两次替换来修正.
请纳入一种交换操作,使得此类相邻字符间的换位错误只需一次操作即可.
状态方程定义如下：
当 P[i] = T[k]时，有
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] , i − 1 ≥ 0 , j − 1 ≥ 0 dp[i][j] = dp[i-1][j-1],i-1\geq0,j-1\geq0 dp[i][j]=dp[i−1][j−1],i−1≥0,j−1≥0
当P[i] = T[j-1]且P[i-1]=T[j]时
d p [ i ] [ j ] = d p [ i − 2 ] [ j − 2 ] + 1 , i − 2 ≥ 0 , j − 2 ≥ 0 dp[i][j] = dp[i-2][j-2] + 1,i-2\geq0,j-2\geq0 dp[i][j]=dp[i−2][j−2]+1,i−2≥0,j−2≥0
否则：
d p [ i ] = m a x { d p [ i − 1 ] [ j − 1 ] + 1 , i − 1 ≥ 0 , j − 1 ≥ 0 d p [ i − 1 ] [ j ] + 1 , i − 1 ≥ 0 d p [ i ] [ j − 1 ] + 1 , j − 1 ≥ 0 dp[i] = max
dp[i]=max⎩⎪⎨⎪⎧dp[i−1][j−1]+1,dp[i−1][j]+1,dp[i][j−1]+1,i−1≥0,j−1≥0i−1≥0j−1≥0
代码请读者自己实现。
评论记录：
回复评论：