动态规划--编辑距离问题
发布日期:2021-07-01 04:22:10 浏览次数:23 分类:技术文章

本文共 1567 字,大约阅读时间需要 5 分钟。

文章目录

1 编辑距离问题

定义: 给定字符串A和字符串B,我们可以进行替换、插入、删除三种操作,使得字符串A和字符串B相等的最小操作次数,称为从字符串A到字符串B的最小编辑距离。

给定字符串“abc”和“dbd”,我们要想得到从“abc”到“dbd”的最小编辑距离,可以有以下几种计算路径:

  • 已知“ab”到“dbd”的编辑距离为x,由于“ab”经过x次操作已经和“dbd”相等,“abc”相对于“ab”来说增加了一个字符’c’,那么“abc”就需要将字符’c’进行删除操作,那么从“abc”到“dbd”的编辑距离就为distance1 = x+1。删除字符操作
  • 已知“ab”到“db”的编辑距离为y,由于“ab”经过y次操作已经和“db”相等,“abc”相对于“ab”增加了一个字符’c’,“dbd”相对于“db”也就只增加了一个字符’d’,此时我们只需要做一步替换操作即可,将’c’替换换成’d’即可,那么从"abc"到"dbd"的编辑距离就为distance = y + 1。替换字符操作
  • 已知“abc”到“db”的编辑距离为z,由于“abc”经过x次操作已经和“db”相等,“dbd”相对于“db”来说增加了一个字符’d’,那么“abc”就需要再增加1个字符“d”,那么从“abc”到“dbd”的编辑距离就为distance1 = z+1。增加字符操作

以上三种情况中的最小值,就是我们求解的最小编辑距离。

我们可以沿着以上思路继续往下分解,直到两个都从空字符开始,我们每次都只保留最优解,然后在此基础上进行递推,这就是动态规划。

递推表格如下:
在这里插入图片描述
我们只需要取3个中间的最小值即可。

写明白还挺难的,先不写了,上面的描述够自己看懂了,直接上代码,哈哈哈哈哈哈。

public static int getStrDistance(String str1, String str2)
{    
if ((str1 == null) || (str2 == null))
{    
return -1;
}
int[][] distance = new int[str1.length()+1][str2.length()+1];
for (int i=0; i
{    
distance[i][0] = i;
}
for (int i=0; i
{    
distance[0][i] = i;
}
for (int i=1; i
{    
for (int j=1; j
{    
int add_distance = distance[i-1][j] + 1;
int del_distance = distance[i][j-1] + 1;
int replace_distance = distance[i-1][j-1];
if (str1.charAt(i-1) != str2.charAt(j-1))
{    
replace_distance += 1;
}
int min = Math.min(add_distance, del_distance);
distance[i][j] = Math.min(min, replace_distance);
}
}
return distance[str1.length()][str2.length()];
}

转载地址:https://muzimin.blog.csdn.net/article/details/102550533 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:vi常用命令汇总
下一篇:C/C++中的数据类型转换

发表评论

最新留言

表示我来过!
[***.249.79.50]2022年04月27日 00时44分04秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章