CODEWITHSUNDEEP
stringalgorithm
user1471283
user1471283

Reputation: 381

Lowest cost to convert one string to another

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')

Upvotes: 3

Views: 4856

Answers (2)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70939

I would solve this problem using dynamic programming. Use a two dimensional array mem[n1][n2] where mem[i][j] stores the minimum cost to convert the suffix of first string starting from position i to the suffix of the second string starting at j.

Your approach seems greedy and also I think it will be extremely slow for bigger examples.

Upvotes: 1

bobah
bobah

Reputation: 18864

You can use the Levenshtein Distance algorithm

Upvotes: 5

Related Questions