Given two strings x and y, What is the cheapest possible way to convert x into y where following operations are allowed to perform –
- Substitute a character c of x with c’.
- Insert a character in x.
- Delete a character from x.
Each of these operations may have a cost associated with them. For example we may have a 26*26 matrix which can have a cost of substituting one character with another character. In a similar manner we may have a 26*2 matrix which can have cost of inserting and deleting a character.