题目大意

给定两个字符串 a 和 b，可以通过删除、插入和替换三种操作将字符串 a 转换为字符串 b。要求计算将字符串 a 转换为字符串 b 的最小代价

思路

该问题类似于编辑距离问题，因此可以考虑使用动态规划来解决。我们定义 dp[i][j] 表示将字符串 a 的前 i 个字符转换为字符串 b 的前 j 个字符的最小代价。

边界情况 当 i 或 j 为 0 时，表示其中一个字符串为空，此时只能通过插入或删除操作将一个字符串转换为另一个。每次插入或删除的代价是 3，因此 dp[i][j] 的值为 (i + j) * 3。

状态转移

题目内容

在无线通信中，每一个基站都会有一个名字，一般同一个区域的基站名字会比较相近，可以通过判断两个基站名字相似程度来识别它是否在同一区域。通过基站间的名字字符串之间转换，来判断两个基站名字的相似度。字符之间的转换只有$3$种操作(增，删，改):

$1$、增:插入一个字符;

$2$、删:删除一个字符;

$3$、改: 替换一个字符;

并且以上$3$种操作分别对应不同的打分项，得分越低，说明相似度越高。

$1$)增 $3$分; $2$) 删 $3$分; $3$)替换，字符在以下两分组内同一组的得$1$分，分别在两个组的得$2$分，其他得$3$分

组$1${$'w', 'i, 'r', 'e','l, '@', 'c', 'o','m'$}

组$2${$'h,'f', 'v',$'#',$'g', 'b', 't', 's'$}

给定两个无线基站名字，请识别出相似度(即字符转换操作的最低得分)。

输入描述

输入两个名字字符串

注:字符串长度范围[1,2000]。

输出描述

输出两者之间的相似度

样例1

输入

chu
xu		

输出

6

说明

基站名字$1$为“$chu$"，基站名字2“$xu$”，进行这两个基站名字间的字符转换步骤:

第$1$步$c$替换为$x: chu -> xhu$，$c$在组$1$内，$x$不在，所以得分$3$

第2步 $h$删除: $xhu -> xu$，得分$3$

总得分为$6$，所以相似度为$6$，输出$6$

样例2

输入

jinhailu
jinzhanglu

输出

8

说明

基站名字$1$为“$jinhailu$"，基站名字$2$“$jinzanglu$"，进行这两个基站名字间的字符转换步骤:

路径$1$:

第$1$步 $h$替换为$z:jinhailu -> jinzailu$，$h$在组$2$，$z$不在，所以得分为$3$

第$2$步 $i$替换为$n$:$jinzailu -> jinzanlu$，$i$在组$1$，$n$不在，所以得分为$3$

第$3$步 插入$g:jinzanlu -> jinzanglu$，得分为$3$

总得分为$7$

路径$2$:

第$1$步 $h$替换为$z:jinhailu -> jinzailu$,$h$在组$2$，$z$不在，所以得分为$3$

第$2$步 插入$n:jinzailu -> jinzanilu$，插入操作得分为$3$

第$3$步 $i$替换为g:$jinzanilu -> jinzanglu$，$i$在组$1$，$g$在组$2$，所以得分为$2$

总得分为$8$

所以路径$2$，得分少，选择路径$2$，输出$8$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写