20ms Detailed Explained C++ Solutions (O(n) Space)


  • 269

    This is a classic problem of Dynamic Programming. We define the state dp[i][j] to be the minimum number of operations to convert word1[0..i - 1] to word2[0..j - 1]. The state equations have two cases: the boundary case and the general case. Note that in the above notations, both i and j take values starting from 1.

    For the boundary case, that is, to convert a string to an empty string, it is easy to see that the mininum number of operations to convert word1[0..i - 1] to "" requires at least i operations (deletions). In fact, the boundary case is simply:

    1. dp[i][0] = i;
    2. dp[0][j] = j.

    Now let's move on to the general case, that is, convert a non-empty word1[0..i - 1] to another non-empty word2[0..j - 1]. Well, let's try to break this problem down into smaller problems (sub-problems). Suppose we have already known how to convert word1[0..i - 2] to word2[0..j - 2], which is dp[i - 1][j - 1]. Now let's consider word[i - 1] and word2[j - 1]. If they are euqal, then no more operation is needed and dp[i][j] = dp[i - 1][j - 1]. Well, what if they are not equal?

    If they are not equal, we need to consider three cases:

    1. Replace word1[i - 1] by word2[j - 1] (dp[i][j] = dp[i - 1][j - 1] + 1 (for replacement));
    2. Delete word1[i - 1] and word1[0..i - 2] = word2[0..j - 1] (dp[i][j] = dp[i - 1][j] + 1 (for deletion));
    3. Insert word2[j - 1] to word1[0..i - 1] and word1[0..i - 1] + word2[j - 1] = word2[0..j - 1] (dp[i][j] = dp[i][j - 1] + 1 (for insertion)).

    Make sure you understand the subtle differences between the equations for deletion and insertion. For deletion, we are actually converting word1[0..i - 2] to word2[0..j - 1], which costs dp[i - 1][j], and then deleting the word1[i - 1], which costs 1. The case is similar for insertion.

    Putting these together, we now have:

    1. dp[i][0] = i;
    2. dp[0][j] = j;
    3. dp[i][j] = dp[i - 1][j - 1], if word1[i - 1] = word2[j - 1];
    4. dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1), otherwise.

    The above state equations can be turned into the following code directly.

    class Solution { 
    public:
        int minDistance(string word1, string word2) { 
            int m = word1.length(), n = word2.length();
            vector<vector<int> > dp(m + 1, vector<int> (n + 1, 0));
            for (int i = 1; i <= m; i++)
                dp[i][0] = i;
            for (int j = 1; j <= n; j++)
                dp[0][j] = j;  
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (word1[i - 1] == word2[j - 1]) 
                        dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = min(dp[i - 1][j - 1] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
                }
            }
            return dp[m][n];
        }
    };
    

    Well, you may have noticed that each time when we update dp[i][j], we only need dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]. In fact, we need not maintain the full m*n matrix. Instead, maintaing one column is enough. The code can be optimized to O(m) or O(n) space, depending on whether you maintain a row or a column of the original matrix.

    The optimized code is as follows.

    class Solution { 
    public:
        int minDistance(string word1, string word2) {
            int m = word1.length(), n = word2.length();
            vector<int> cur(m + 1, 0);
            for (int i = 1; i <= m; i++)
                cur[i] = i;
            for (int j = 1; j <= n; j++) {
                int pre = cur[0];
                cur[0] = j;
                for (int i = 1; i <= m; i++) {
                    int temp = cur[i];
                    if (word1[i - 1] == word2[j - 1])
                        cur[i] = pre;
                    else cur[i] = min(pre + 1, min(cur[i] + 1, cur[i - 1] + 1));
                    pre = temp;
                }
            }
            return cur[m]; 
        }
    }; 
    

    Well, if you find the above code hard to understand, you may first try to write a two-column version that explicitly maintains two columns (the previous column and the current column) and then simplify the two-column version into the one-column version like the above code :-)


  • 0
    S
    This post is deleted!

  • 3
    S

    thanks a lot ,this is the most concise explanation i've ever seen about the problem


  • 1

    Hi, stealflowercow. You are very welcome.


  • 6
    Y

    Hi ianchao.li.fighter,
    I don't understand when word[i - 1] and word2[j - 1] are equal, dp[i][j] can directly set to dp[i - 1][j - 1] rather than dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1). I know there must be some straight forward reason but I just can't figure it out. Could you help me explain this?


  • 2

    Hi, yanzhe-chen. Well, since the two sub-strings corresponding to dp[i - 1][j - 1] are not longer than those of both dp[i - 1][j] and dp[i][j - 1], so I guess dp[i – 1][j – 1] will be smaller than both dp[i – 1][j] and dp[i][j – 1] and so we need not use min.


  • 14
    W

    Actually 99% people just google it for solution. I'm glad you asked that question yanzhe-chen. The idea is: Any adjacent value in the matrix dp can only diff by 1. So dp[i - 1][j - 1] <= dp[i – 1][j] + 1. Otherwise we can first transform to dp[i – 1][j] then do one operation to dp[i - 1][j - 1] and the dp[i-1][j-1] would no longer be the minimum distance. The same to dp[i][j – 1]


  • 1

    Thank @whamrx for the great explanation!


  • 1
    S

    Brilliant! thx for the detail explanation, how can u figure out this wonderful solution


  • 0
    B
    This post is deleted!

  • 0
    B

    Thanks, real good explanation!!!


  • 3
    H

    I know whamrx has provided great explanation, but I just want to provide my personal understanding.

    That's because each cell contains the MIN effort to match two subStrings ended at this cell.
    So if current char pair match, then we need to look up the MIN effort to match subStrings ended at [i-1, j-1], which means we need to look up cell[i-1][j-1]


  • 0
    S

    I wrote a python version of this simplified algorithm. Nice! I originally maintained a m*n matrix for the dp transition. this passed the tests with around 280ms.

    class Solution(object):
          def minDistance(self, word1, word2):
                l1=len(word1); l2=len(word2)
                track= range(l1+1)
        
               for j in xrange(1, l2+1):
                   pre=track[0];track[0]=j
                   for i in xrange(1,l1+1):
                       temp=track[i]
                       track[i]=min(pre+ (word1[i-1]!=word2[j-1]), min(track[i-1], track[i])+1)
                       pre=temp
               return track[-1]

  • 4
    J

    Thank the author for the detailed explanation! I still don't understand. I think it assume that from word1 to word2, We can only change the LAST letter(change or add or delete). Why we cannot change other than the LAST letter? For example, from 'sabc' to 'abcd' how the algorithm works on this case?


  • 0
    Z

    I'm also confused...Do you figure it out now?


  • 0
    T

    For insertion and deletion difference: is insertion to word1 the same as deletion from word2?


  • 0
    O

    thanks for the work


  • 0
    V

    It's ok.You can try it step by step, for example 'sa' to 'a', and dp[2][1] = 1.


  • 0
    V

    You can see my reply, hope it helps.


  • 1
    T

    python version:

    def minDistance(self, word1, word2):
            L1, L2 = len(word1), len(word2)
            dp = range(L1+1)
            for i in range(L2):
                lasti_1, dp[0] = dp[0], dp[0]+1
                for j in range(1, L1+1):
                    lasti_1, dp[j] = dp[j], min(dp[j-1]+1, dp[j]+1, lasti_1+int(word1[j-1] != word2[i]))
            return dp[L1]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.