C++ O(n)-space DP
To apply DP, we define the state dp[i][j] to be the minimum number of operations to convert word1[0..i) to word2[0..j).\n\nFor the base case, that is, to conver
To apply DP, we define the state `dp[i][j]` to be the minimum number of operations to convert `word1[0..i)` to `word2[0..j)`.\n\nFor the base case, that is, to convert a string to an empty string, the mininum number of operations (deletions) is just the length of the string. So we have `dp[i][0] = i` and `dp[0][j] = j`.\n\nFor the general case to convert `word1[0..i)` to `word2[0..j)`, we break this problem down into sub-problems. Suppose we have already known how to convert `word1[0..i - 1)` to `word2[0..j - 1)` (`dp[i - 1][j - 1]`), if  `word1[i - 1] == word2[j - 1]`, then no more operation is needed and `dp[i][j] = dp[i - 1][j - 1]`.\n\nIf `word1[i - 1] != word2[j - 1]`, we need to consider three cases.\n\n 1. **Replace** `word1[i - 1]` by `word2[j - 1]` (`dp[i][j] = dp[i - 1][j - 1] + 1`);\n 2. If `word1[0..i - 1) = word2[0..j)` then **delete** `word1[i - 1]` (`dp[i][j] = dp[i - 1][j] + 1`);\n 3. If `word1[0..i) + word2[j - 1] = word2[0..j)` then **insert** `word2[j - 1]` to `word1[0..i)` (`dp[i][j] = dp[i][j - 1] + 1`).\n\nSo when `word1[i - 1] != word2[j - 1]`, `dp[i][j]` will just be the minimum of the above three cases.\n\n```cpp\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int m = word1.size(), n = word2.size();\n        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));\n        for (int i = 1; i <= m; i++) {\n            dp[i][0] = i;\n        }\n        for (int j = 1; j <= n; j++) {\n            dp[0][j] = j;\n        }\n        for (int i = 1; i <= m; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (word1[i - 1] == word2[j - 1]) {\n                    dp[i][j] = dp[i - 1][j - 1];\n                } else {\n                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;\n                }\n            }\n        }\n        return dp[m][n];\n    }\n};\n```\n\nNote that each time when we update `dp[i][j]`, we only need `dp[i - 1][j - 1]`, `dp[i][j - 1]` and `dp[i - 1][j]`. We may optimize the space of the code to use only two vectors.\n\n```cpp\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int m = word1.size(), n = word2.size();\n        vector<int> pre(n + 1, 0), cur(n + 1, 0);\n        for (int j = 1; j <= n; j++) {\n            pre[j] = j;\n        }\n        for (int i = 1; i <= m; i++) {\n            cur[0] = i;\n            for (int j = 1; j <= n; j++) {\n                if (word1[i - 1] == word2[j - 1]) {\n                    cur[j] = pre[j - 1];\n                } else {\n                    cur[j] = min(pre[j - 1], min(cur[j - 1], pre[j])) + 1;\n                }\n            }\n            fill(pre.begin(), pre.end(), 0);\n            swap(pre, cur);\n        }\n        return pre[n];\n    }\n};\n```\n\nOr even just one vector.\n\n```cpp\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        int m = word1.size(), n = word2.size(), pre;\n        vector<int> cur(n + 1, 0);\n        for (int j = 1; j <= n; j++) {\n            cur[j] = j;\n        }\n        for (int i = 1; i <= m; i++) {\n            pre = cur[0];\n            cur[0] = i;\n            for (int j = 1; j <= n; j++) {\n                int temp = cur[j];\n                if (word1[i - 1] == word2[j - 1]) {\n                    cur[j] = pre;\n                } else {\n                    cur[j] = min(pre, min(cur[j - 1], cur[j])) + 1;\n                }\n                pre = temp;\n            }\n        }\n        return cur[n];\n    }\n};\n```
['Dynamic Programming', 'C++']