Help with Dynamic Programming. Edit Distance (15) Given two text strings A of le

Question

Help with Dynamic Programming.

Edit Distance (15) Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B. Describe a dynamic programming algorithm (no need to code) to find the edit distance between two strings Using this algorithms find the edit distance from the string "sail ship" to the string "sales boy". Show all your steps.

Explanation / Answer

There were two possibilities to implement the given questions. Let us consider two variables m and n

a: lenght of first string (i.e., sailship)

b: length of second string (i.e., sales boy)

(i) If last characters of each string were same then ignore the last characters then we can recur for lengths a-1 and b-1 .( In our case we can go througth this step )

(ii) Else ( if last characters were not same ) then we have to consider the below three operations on a(first string) , recursively compute minimum cost for below three operations and take minimum of three values.

a. insert - recur for a and b-1

b. delete - recur for a-1 and b

c. replace - recur for a-1 and b-1

Let me implement the program in Java

class Edistance{

static int min(int x, int y, int z)

{

if(x<y && x<z)

return x;

if (y<x && y<z)

return y;

else

return z;

}

static int EditDistance(String st1, String st2, int a, int b)

{

if(a==0)

return b;

if(b==0)

return a;

if(st1.charAt(a-1)==st2.charAt(n-1))

return EditDistance(st1,st2,m-1,n-1);

return 1+min(EditDistance(st1,st2,a,b-1),

(EditDistance(st1,st2,a-1,b),

(EditDistance(st1,st2,m-1,n-1));

}

public static void main(String args[])

{

String st1="sailship";

String st2="sales boy";

System.Out.println(st1,st2,st1.length(),st2.length());

}

}

I hope this answer will help you.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.