### Distance between two strings

Problem: what is the cheapest way to transform one

word (the source) into another word (the output)?

At any point, you can:

Delete the current character of the source.

Insert a new character into the output word.

Copy the current character of the source into the output.

Each operation has a cost associated with it.

The cost of a transformation is the sum of the costs

of each operation in the sequence.

Example: “algorithm” “alligator”

Operations: Copy, Copy, Insert(l), Insert(i), Copy

Delete, Delete, Delete, Insert(a), Copy, Delete,

Delete, Insert(o), Insert(r)

Assume that:

Copying costs 3

Inserting costs 5

Deleting costs 2

The cost of the above transformation is: 47

This is just 3 + 3 + 5 + 5 + 3 + 2 + 2 + ...

Wap to find the minimum cost.

word (the source) into another word (the output)?

At any point, you can:

Delete the current character of the source.

Insert a new character into the output word.

Copy the current character of the source into the output.

Each operation has a cost associated with it.

The cost of a transformation is the sum of the costs

of each operation in the sequence.

Example: “algorithm” “alligator”

Operations: Copy, Copy, Insert(l), Insert(i), Copy

Delete, Delete, Delete, Insert(a), Copy, Delete,

Delete, Insert(o), Insert(r)

Assume that:

Copying costs 3

Inserting costs 5

Deleting costs 2

The cost of the above transformation is: 47

This is just 3 + 3 + 5 + 5 + 3 + 2 + 2 + ...

Wap to find the minimum cost.

int LevenshteinDistance(char s[1..m], char t[1..n])

ReplyDelete{

// d is a table with m+1 rows and n+1 columns

declare int d[0..m, 0..n]

for i from 0 to m

d[i, 0] := i // deletion

for j from 0 to n

d[0, j] := j // insertion

for j from 1 to n

{

for i from 1 to m

{

if s[i] = t[j] then

d[i, j] := d[i-1, j-1]

else

d[i, j] := minimum

(

d[i-1, j] + 1, // deletion

d[i, j-1] + 1, // insertion

d[i-1, j-1] + 1 // substitution

)

}

}

return d[m,n]

}

Dint get u..Would u plz elaborate ur approach :(

ReplyDelete