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

• 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 :-)

• This post is deleted!

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

• Hi, stealflowercow. You are very welcome.

• 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?

• 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`.

• 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]`

• Thank @whamrx for the great explanation!

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

• This post is deleted!

• Thanks, real good explanation!!!

• 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]

• 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]``````

• 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?

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

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

• thanks for the work

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

• You can see my reply, hope it helps.

• 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]``````

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