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.