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.

Comments

  1. int LevenshteinDistance(char s[1..m], char t[1..n])
    {
    // 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]
    }

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

    ReplyDelete

Post a Comment

Popular posts from this blog