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