假设我们要使用的操作只有3个类型中的一种字符串S1转换为另一个字符串S2：

   - 插入（POS，字符）（成本8）
 - 删除（POS）（成本6）
-replace（POS，字符）（成本8）
 

找到的步骤的顺序来转换S1至S2，使得至S1转换到S2成本最小。 例如。 计算到晚 - 可能的操作是

 删除（0）
删除（1）
删除（2）
删除（3）
删除（4）
 

和上述操作序列费30。

我使用下面的code要做到这一点，但它没有给予正确的结果。 所使用的算法是的Levenshtein

 元组= []
OPS = []
S1 =''
S2 =''
高清莱文斯坦（A，B）：
    全球S1，S2
    N，M = len个（一），LEN（二）
    如果n＆GT; M：
        的a，b = B，A
        N，M = M，N
    S1，S2 = A，B
    电流=范围第（n + 1）
    因为我在范围（0，len个（电流））：
        目前的[I] =电流（I）* 8
    tuples.append（电流）
    对于i在范围（1，M + 1）：
        previous，电流=电流[I * 8] + [0] * N
        对于j在范围（1，N + 1）：
            添加，删除= previous [J] +6，目前的研究[J-1] +8
            更改= previous [J-1]
            如果一个[J-1] = B [I-1]！：
                变化=改变+ 8
            目前的研究[J] = MIN（添加，删除，更改）
        tuples.append（电流）
    返回电流[N]
打印莱文斯坦（计算，晚）
 

解决方案

您可以使用 Levenshtein距离算法

Suppose we want to convert one string S1 to another string S2 using only 3 types of operations:

-Insert(pos,char) (costs 8)
-Delete(pos) (costs 6)
-Replace(pos,char) (costs 8)

Find the sequence of steps to convert S1 to S2 such that the cost to convert S1 to S2 is minimum. Eg. 'calculate' to 'late' - the possible operations are

Delete(0)
Delete(1)
Delete(2)
Delete(3)
Delete(4)

and the above sequence of operations costs 30.

I am using the following code to do this but its not giving correct results. The algorithm used is Levenshtein.

tuples=[]
ops=[]
s1=''
s2=''
def levenshtein(a,b):
    global s1,s2
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n
    s1,s2=a,b
    current = range(n+1)
    for i in range(0,len(current)):
        current[i]=current[i]*8
    tuples.append(current)
    for i in range(1,m+1):
        previous, current = current, [i*8]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+6, current[j-1]+8
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change=change+8
            current[j] = min(add, delete, change)
        tuples.append(current)
    return current[n]
print levenshtein('calculate','late')

You can use the Levenshtein Distance algorithm