WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Edit Distance Overview
What is Edit Distance?
The edit distance between two strings is the minimum number of operations required to transform one string into the other. The operations are typically insertion, deletion, or substitution of a single character.
Example 1: Simple Substitution
Transforming "cat" to "bat"
In this example, we only need one substitution operation: change 'c' to 'b'. Thus, the edit distance is 1.
String str1 = "cat";
String str2 = "bat";
// Edit distance is 1 due to single substitution
Example 2: Insertion and Deletion
Transforming "kitten" to "sitting"
This transformation involves two substitutions ('k' to 's', 'e' to 'i') and one insertion ('g'). Therefore, the edit distance is 3.
String str1 = "kitten";
String str2 = "sitting";
// Edit distance is 3: 2 substitutions, 1 insertion
Example 3: Multiple Operations
Transforming "flaw" to "lawn"
This requires two substitutions ('f' to 'l', 'w' to 'n'). The edit distance is 2.
String str1 = "flaw";
String str2 = "lawn";
// Edit distance is 2: 2 substitutions
Example 4: Insertions Only
Transforming "abc" to "abcd"
This transformation involves one insertion operation: adding 'd' at the end. The edit distance is 1.
String str1 = "abc";
String str2 = "abcd";
// Edit distance is 1: 1 insertion
Example 5: Deletions Only
Transforming "hello" to "hell"
This transformation involves one deletion operation: removing 'o'. The edit distance is 1.
String str1 = "hello";
String str2 = "hell";
// Edit distance is 1: 1 deletion
