Algorithm Tutorials | Dynamic Programming | Minimum Edit Distance.md

What is Minimum Edit Distance?

Convert a string into a another string by using minimum number of operations.

ex: Convert "dog" into "cat"

• 1.modify "d" into "c"
• 2.modify "o" into "a"
• 3.modify "g" into "t"
  So we have to do 3 operations.

Minimum Edit Distance By Using Dynamic Programming

• Draw memoization matrix.

• Write converting string's characters along y axis and converted string along x axis.

• Fill matrix using below rules.

  Rules

  • Use arrow signs to reperesent operation done
    ➡️ for Insert operation
    ⬇️ for remove operation
    ↘️ for modify operation

  • If row character is equal to coloumn character just copy the dioganal value.

  • If row character is not equal to coloumn character find the minimum value among top cell,left cell and dioganal cell with respect to the cell we finding the value. Then increase that value by 1 and store it.

  • Note: If two there are more than one minimum values in cells just take any minimum valued cell as you wish.

Question: Convert "CART" into "MARCH" ?

• Fill all the values in first row and colomun

  	NULL	M	A	R	C	H
  NULL	0	1	2	3	4	5
  C	1
  A	2
  R	3
  T	4

  • explanation:
    At row 1,colomn 1: To make NULL into NULL we don't need to do operation.
    At row 1,colomn 2: To make NULL into "M" we have to insert "M". 1 operation.
    At row 1,colomn 3: To make NULL into "MA" we have to insert "M" and "A". 2 operations. And rest also do the same.
    At row 2,colomn 1: To make "C" into NULL we have to delete "C". 1 operation.
    At row 3,colomn 1: To make "CA" into NULL we have to delete "C" and "A". 2 operations. And rest also do the same.

• Compare "C" and "M". They do not match. So get minimum value from top,left and dioganal cells. Minimum is 0. Now increase it by 1. And store in the matrix.

  	NULL	M	A	R	C	H
  NULL	0	1	2	3	4	5
  C	1	↘️1
  A	2
  R	3
  T	4

  • explanation:
    At row 2,colomn 2: To make "C" into "M" we have to modify "C" as "M". 1 operation.

• Compare "C" and "A". They do not match. So get minimum value from top,left and dioganal cells. So there are two Minimums as 1. Take any value and increase it by 1. And store in the matrix. Note: Draw the arrow from element you taken as the minimum. Here it taken from left minimum value.

  	NULL	M	A	R	C	H
  NULL	0	1	2	3	4	5
  C	1	↘️1	➡️ 2
  A	2
  R	3
  T	4

  • explanation:
    At row 2,colomn 3: To make "C" into "MA" we have to modify "C" as "M" and insert "A". 2 operations. And rest of the matrix will be filled like this.

• Final matrix will look like this.

  	NULL	M	A	R	C	H
  NULL	0	1	2	3	4	5
  C	1	↘️1	➡️2	➡️3	↘️3	➡️4
  A	2	↘️2	↘️1	➡️2	➡️3	➡️4
  R	3	↘️3	⬇️2	↘️1	➡️2	➡️3
  T	4	↘️4	⬇️3	⬇️2	↘️2	➡️3

• Now we can see we have to do 3 operations to convert "CART" into "MARCH". Let's see how it happened.

  	NULL	M	A	R	C	H
  NULL	**0	1	2	3	4	5
  C	1	**:arrow_lower_right:1	➡️2	➡️3	↘️3	➡️4
  A	2	↘️2	**:arrow_lower_right:1	➡️2	➡️3	➡️4
  R	3	↘️3	⬇️2	**:arrow_lower_right:1	➡️2	➡️3
  T	4	↘️4	⬇️3	⬇️2	**:arrow_lower_right:2	**:arrow_right:3

  • Now you can see path towards double astrixes cells shows which operations we have done.
  • As it mentioned before ➡️ insert, ↘️ modify, ⬇️ remove
  • cell(T,H) has ➡️. So it is a insertion. So the total operations are 1.
  • cell(T,C) has ↘️ and characters "T" and "C" are not equal. So it must be deletion/remove. So the total operations are 2.
  • cell(R,R) has ↘️ and characters "R" and "R" are equal. So we don't need to perform any operation. So the total operations are 2.
  • cell(A,A) has ↘️ and characters "A" and "A" are equal. So we don't need to perform any operation. So the total operations are 2.
  • cell(C,M) has ↘️ but characters "C" and "M" are not equal. So it must be deletion/remove. So the total operations are 3.