he edit distance is the minimum number of character insertions and character deletions required to turn one string into another. Compute the edit distance between each pair of the strings he, she, his, and hers.
To compute the edit distance between each pair of the strings "he", "she", "his", and "hers," we can use a dynamic programming algorithm called the Wagner-Fischer algorithm. This algorithm calculates the minimum number of operations (insertions, deletions, and substitutions) required to transform one string into another.
Here's how we can apply the Wagner-Fischer algorithm step by step:
1. Initialize a (n+1) x (m+1) matrix, where n is the length of the first string and m is the length of the second string. This matrix will be used to store the intermediate edit distances between substrings.
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | | | |
| h | | | |
| e | | | |
| r | | | |
| s | | | |
2. Fill in the first row and first column of the matrix with values from 0 to n and 0 to m, respectively. These values represent the number of deletions required to transform an empty string into the corresponding substring.
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | 1 | | |
| h | 2 | | |
| e | 3 | | |
| r | 4 | | |
| s | 5 | | |
3. For each cell in the matrix (except the first row and first column) starting from the second row and second column:
- Calculate the cost of each operation (insertion, deletion, and substitution) needed to transform the character in the first string into the character in the second string.
- Take the minimum cost among the three possibilities and store it in the current cell.
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | 1 | 1 | 2 |
| h | 2 | | |
| e | 3 | | |
| r | 4 | | |
| s | 5 | | |
Repeat this process for the remaining cells:
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | 1 | 1 | 2 |
| h | 2 | 2 | 3 |
| e | 3 | 3 | 3 |
| r | 4 | | |
| s | 5 | | |
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | 1 | 1 | 2 |
| h | 2 | 2 | 3 |
| e | 3 | 3 | 3 |
| r | 4 | 4 | 4 |
| s | 5 | | |
| | | h | e |
|---|---|---|---|
| | 0 | 1 | 2 |
| s | 1 | 1 | 2 |
| h | 2 | 2 | 3 |
| e | 3 | 3 | 3 |
| r | 4 | 4 | 4 |
| s | 5 | 5 | 4 |
4. The minimum edit distance between the two strings is the value in the bottom-right cell of the matrix.
In this case, the edit distances between the given strings are:
- "he" and "she" have an edit distance of 2.
- "he" and "his" have an edit distance of 2.
- "he" and "hers" have an edit distance of 3.
- "she" and "his" have an edit distance of 1.
- "she" and "hers" have an edit distance of 2.
- "his" and "hers" have an edit distance of 2.
Therefore, the edit distances between each pair of strings are as follows:
- "he" and "she" -> 2
- "he" and "his" -> 2
- "he" and "hers" -> 3
- "she" and "his" -> 1
- "she" and "hers" -> 2
- "his" and "hers" -> 2