Minimum edit distance of two strings - Ritambhara - Coding Interview Preparations

Minimum edit distance of two strings – Ritambhara – Coding Interview Preparations

Insert(pos, ch) – Insert a character at a position in the string. Delete(position) – Delete a character from a position in the string. Replace(position, character) – Replace a particular character with some other character at a position in the string. For example, If input strings are ‘KITTEN‘ and ‘SITTING‘ then the edit distance between them is 3. kitten -> sitten (Replace) sitten -> sittin (Replace) sittin -> sitting (Insert) It can be used in applications like auto spell correction to correct a wrong spelling and replace it with the nearest (minim distance) word. This can be more complex, and may not be intuitive. For example, the distance between two strings INTENTION and EXECUTION. then the minimum distance is 5. Recursive Solution: We start from the first character and for each character, we do the following: IF (characters of two strings are same) Ignore that characters and get count for remaining strings. (Recursively call the function for lengths m-1 and n-1).

Read full article from Minimum edit distance of two strings – Ritambhara – Coding Interview Preparations