Real-World Applications of Edit Distance
- Spell Checking and Auto-Correction
- DNA Sequence Alignment
- Plagiarism Detection
- Natural Language Processing
- Version Control Systems
- String Matching
https://youtu.be/Thv3TfsZVpw
Edit Distance
Given two strings str1 and str2 of length M and N respectively and below operations that can be performed on str1. Find the minimum number of edits (operations) to convert ‘str1‘ into ‘str2‘.
- Operation 1 (INSERT): Insert any character before or after any index of str1
- Operation 2 (REMOVE): Remove a character of str1
- Operation 3 (Replace): Replace a character at any index of str1 with some other character.
Note: All of the above operations are of equal cost.
Examples:
Input: str1 = “geek”, str2 = “gesek”
Output: 1
Explanation: We can convert str1 into str2 by inserting a ‘s’ between two consecutive ‘e’ in str2.Input: str1 = “cat”, str2 = “cut”
Output: 1
Explanation: We can convert str1 into str2 by replacing ‘a’ with ‘u’.Input: str1 = “sunday”, str2 = “saturday”
Output: 3
Explanation: Last three and first characters are same. We basically need to convert “un” to “atur”. This can be done using below three operations. Replace ‘n’ with ‘r’, insert t, insert a
Illustration of Edit Distance:
Let’s suppose we have str1=”GEEXSFRGEEKKS” and str2=”w3wiki”
Now to convert str1 into str2 we would require 3 minimum operations:
Operation 1: Replace ‘X‘ to ‘K‘
Operation 2: Insert ‘O‘ between ‘F‘ and ‘R‘
Operation 3: Remove second last character i.e. ‘K‘Refer the below image for better understanding.
Contact Us