时间戳

首页 > 解决方案 > 两根弦之间的最小距离

algorithm - 两根弦之间的最小距离

问题描述

给定 2 个字符串A，B。我们可以在其中插入一些字符' - '。

示例：X=" abedf "，我们可以插入 -> " ab--edf- " 或 " ab-e-df " ...

我们称 A 和 B 的距离为abs(ASCII(A[i]-ASCII(B[i]))。但如果 A[i] 或 B[i] 为 '-'，则值为K。我们必须找到它们的最小距离。

例子：

一个=“厘米”

乙=“ scmn ”

K= 2

我们可以插入到

答：“ -cmc ”

B：“ s-nmn- ”

所以距离是10。

标签： algorithmdynamic-programming

解决方案

让 A,B 成为给定的字符串。

请注意，我们最多会插入“-”，以使两个字符串不相互接触：

 d("cmc","scmn")<= d("cmc----","---scmn") =7*2=14

另请注意，插入"-" over "-"（第一个在 A 中，第二个在 B 中）是无用的，因为它只会增加距离2

另外，如果这些操作是合法的，让d(i,j)我们成为，并且 ow （因为）ABS(ASCI(A[i]-B[j]))d(i,j) = 2i>len(A) or j>len(B)

现在，让c(i,k)成为 A[:i] 和 B[:j] 的最小距离

我们会照顾c(2\*max(len(A),len(B)),2*max(len(A),len(B)))的。

请注意c(0,0)=0.

一般情况是：

c(i,k) =min of these cases:

 - d(i,k) + c(i+1,k+1)
 - 2 + c(i+1,k)
 - 2 + c(i,k+1)

推荐阅读