# C++ DP with Explanation

• The allowed operation is "Delete" only, but actually the "Delete" operation on both strings is equal to "Delete" and "Add" on just one string. Then the problem becomes straightforward, given a src string word1 and target string word2, and the allowed operations are "Delete" or "Add" a letter on the source string, we just need to find the minimum operations to convert to the target string.

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

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