# My O(mn) time and O(n) space solution using DP with explanation

• Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):

if c == d, then : f[i][j] = f[i-1][j-1]

Otherwise we can use three operations to convert word1 to word2:

(a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;

(b) if we added d after c: f[i][j] = f[i][j-1] + 1;

(c) if we deleted c: f[i][j] = f[i-1][j] + 1;

Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).

`````` int minDistance(string word1, string word2) {

int l1 = word1.size();
int l2 = word2.size();

vector<int> f(l2+1, 0);
for (int j = 1; j <= l2; ++j)
f[j] = j;

for (int i = 1; i <= l1; ++i)
{
int prev = i;
for (int j = 1; j <= l2; ++j)
{
int cur;
if (word1[i-1] == word2[j-1]) {
cur = f[j-1];
} else {
cur = min(min(f[j-1], prev), f[j]) + 1;
}

f[j-1] = prev;
prev = cur;
}
f[l2] = prev;
}
return f[l2];

}
``````

Actually at first glance I thought this question was similar to Word Ladder and I tried to solve it using BFS(pretty stupid huh?). But in fact, the main difference is that there's a strict restriction on the intermediate words in Word Ladder problem, while there's no restriction in this problem. If we added some restriction on intermediate words for this question, I don't think this DP solution would still work.

• I like your solution. It's nice and concise!

• Thank you!!
According to your idea, I rewrote the code in Java:

``````public class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();

//distance[i][j] is the distance converse word1(1~ith) to word2(1~jth)
int[][] distance = new int[len1 + 1][len2 + 1];
for (int j = 0; j <= len2; j++)
{distance[0][j] = j;} //delete all characters in word2
for (int i = 0; i <= len1; i++)
{distance[i][0] = i;}

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) { //ith & jth
distance[i][j] = distance[i - 1][j - 1];
} else {
distance[i][j] = Math.min(Math.min(distance[i][j - 1], distance[i - 1][j]), distance[i - 1][j - 1]) + 1;
}
}
}
return distance[len1][len2];
}
``````

}

• good solution

• According to your 1D array space, I modified my original one into this O(n) space version. Also pasting original version for reference.

``````public class Solution {
public int minDistance(String word1, String word2) {
int opt[] = new int[word2.length()+1];
// base case
for(int j = 0;j <= word2.length();j++) opt[j] = j;
// iteration
for(int i = 1;i <= word1.length();i++){
int pre = i, corner = i-1;
for(int j = 1;j <= word2.length();j++){
int temp = corner;
corner = opt[j];
temp += (word1.charAt(i-1)==word2.charAt(j-1)?0:1);
opt[j] = Math.min(temp,Math.min(opt[j],pre)+1);
pre = opt[j];
}
opt[word2.length()] = pre;
}
return opt[word2.length()];
}
}
``````

Original Version

``````public class Solution {
public int minDistance(String word1, String word2) {
int opt[][] = new int[word1.length()+1][word2.length()+1];
// base case
for(int i = 0;i <= word1.length();i++) opt[i][0] = i;
for(int j = 0;j <= word2.length();j++) opt[0][j] = j;
// iteration
for(int i = 1;i <= word1.length();i++)
for(int j = 1;j <= word2.length();j++)
opt[i][j] = Math.min(Math.min(opt[i-1][j]+1,opt[i][j-1]+1),opt[i-1][j-1] + (word1.charAt(i-1)==word2.charAt(j-1)?0:1));
return opt[word1.length()][word2.length()];
}
}``````

• Hi, siyang, thank you for your posting. But I have a confusion in your 1-D array version.
Isn't "opt[word2.length()] = pre;" redundant since you've alreay did that in the for loop above with "opt[j] = Math.min(temp,Math.min(opt[j],pre)+1)" ?

Okay, never mind. I just figured out that the reason to keep that line is to handle cases where word2.length() == 0.

• Beautiful code ! Thanks for sharing!

• Hi,
Mine is not optimized, but a simple DP solution, can you please tell me the complexity of my code?

``````    class Solution {
public:
int minDistance(string word1, string word2) {
cache=vector<vector<int>>(word1.size()+1, vector<int>(word2.size()+1,-1));
return minDistance(word1, 0,  word2, 0);
}
private:
int minDistance(const string& word1, int a, const string& word2, int b) {
if(a==word1.size() && b==word2.size()) return 0;
if(a==word1.size()) return word2.size()-b;
if(b==word2.size()) return word1.size()-a;
if(cache[a][b]!=-1) return cache[a][b];

if(word1[a]==word2[b]){
return cache[a][b]=minDistance(word1, a+1, word2, b+1);
}else{
return cache[a][b]=min(min(minDistance(word1,a+1,word2,b+1),
minDistance(word1,a,word2,b+1)),
minDistance(word1,a+1,word2,b))+1;
}
}
vector<vector<int>> cache;
};``````

• So beautiful.

• No better explanation than this one. Thumbs up!

• it should be the same as iterative solution O(n * m), the dfs time depends on the combination of your two parameters, a, and b;

• This post is deleted!

• Good job, recalls me the famous LCS problem.

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