两个字符串之间的最小距离

Question

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

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

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

示例：

A="cmc"

B="scmn"

K=2

我们可以插入到

A：“-c-m-c”

B：“s-nmn-”

所以距离是10.

Answer 1

设A,B为给定的字符串。

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

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

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

此外，如果这些操作合法，让d(i,j)成为ABS(ASCI(A[i]-B[j]))，并且o.w d(i,j) = 2（因为i>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)

Minium distance between two strings