Mark As Completed Discussion

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:

besT
01234
t11233
e22123
s33212
T44321 (*)

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.