Also only one problem for this week due to the overall homework workload. The edit distance is a traditional term evaluating how similar two strings are, and is widely used in applications.

72 Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

My accepted code can be found here

I don’t quite know how to solve the problem at first. Solving this problem by searching seems to take a lot of time. And I peek the discussion, and all they talk about is solving the problem in O(mn), and I know something.

This problem should be solvable by dynamic programming and after the construction of dp matrix, time complexity is O(mn). So the problem now becomes constructing the dp equation.

In base case, both strings should be empty and the edit distance between them is 0. And obviously edit distance between empty string and another string is the length of another string. For non-empty strings, there’re three operations:

  • Add a character to the substring
  • Delete a character from its “superstring”
  • Change a character if the last character of two strings are different

And the result should be the minimum distance among these three method. But problem is we have cannot obtain the minimum distance of some string’s super-string before obtain the distance of itself. If we go multiple round and the time complexity may not be O(mn) then. So how do I know after adding a character, what is the minimum distance of its supestring to another string?

It’s a mysterious here, but it turns out we don’t need to care the adding operation here since we’re constantly adding character through the dynamic programming process. And adding a character which result in the heads of two strings being the same, which may obtain a shorter distance.

So overall the DP equation is like this:

for input s1 and s2
let dp = int[length(s1) + 1][length(s2) + 2]
for all i in range:
    dp[0][i] = dp[i][0] = i

for other i, j in range:
    dp[i][j] = min(
        dp[i][j - 1] + 1,
        dp[i - 1][j] + 1,
        dp[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1))

And the time complexity and space complexity are both O(mn).

However, there’s a chance of optimization of space. Since when we are constructing the dp array, all we want to know is dp[i - 1][j], dp[i][j - 1] and dp[i - 1][j - 1], other spaces are just wasted. So maintaining two rows simultaneously is enough for the problem. So the space complexity can be reduced to O(min(m, n))

Last

There’re wayyyy tooooooo much homework these weeks, so I have to spend a lot more time on those ones and a lot less time on this…So…