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 
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]):\n\nif c == d, then : f[i][j] = f[i-1][j-1]\n\nOtherwise we can use three operations to convert word1 to word2:\n\n(a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1;\n\n(b) if we added d after c: f[i][j] = f[i][j-1] + 1;\n\n(c) if we deleted c: f[i][j] = f[i-1][j] + 1;\n\n\nNote 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]). \n\n\n\n     int minDistance(string word1, string word2) {\n        \n            int l1 = word1.size();\n            int l2 = word2.size();\n        \n            vector<int> f(l2+1, 0);\n            for (int j = 1; j <= l2; ++j)\n                f[j] = j;\n        \n            for (int i = 1; i <= l1; ++i)\n            {\n                int prev = i;\n                for (int j = 1; j <= l2; ++j)\n                {\n                    int cur;\n                    if (word1[i-1] == word2[j-1]) {\n                        cur = f[j-1];\n                    } else {\n                        cur = min(min(f[j-1], prev), f[j]) + 1;\n                    }\n        \n                    f[j-1] = prev;\n                    prev = cur;\n                }\n                f[l2] = prev;\n            }\n            return f[l2];\n        \n        }  \n\n\nActually 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.
[]