Decoding the Matrix: The Final Edit Distance
After filling in our matrix, we look to the bottom-right corner to find our final edit distance. In this example, that value is 1, which confirms that it takes just a single edit to transform "best" into "test". Specifically, we can swap the first b with a t.
Here's the final matrix for quick reference:
| b | e | s | T | ||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | |
| t | 1 | 1 | 2 | 3 | 3 |
| e | 2 | 2 | 1 | 2 | 3 |
| s | 3 | 3 | 2 | 1 | 2 |
| T | 4 | 4 | 3 | 2 | 1 (*) |
Complexity Analysis of the Final Solution
Space Complexity
The matrix we've built has dimensions that depend on the lengths of our two strings. Specifically, if m and n are the lengths of the two strings, the matrix is of size m x n. This gives us a space complexity of O(m x n).
Time Complexity
To fill in this matrix, we used two nested loops that iterate through each row and column, performing constant-time operations at each cell. This results in a time complexity of O(m x n) as well.
Both the time and space complexities for this solution are O(m x n), making it a quadratic algorithm.