# C++ 6 lines DP O(n * m) and 4 lines DFS + Memo

• 1. DP
The transition function is the minimum of three cases:

• Skip character in both string (dp[i - 1][j - 1]).
• Add two deleted characters if the character is different
• Add zero deleted characters if the character is the same (w1[i] == w2[j])
• Skip character in the first string (dp[i - 1][j]). Add one deleted character
• Skip character in the second string (dp[i][j - 1]). Add one deleted one character
``````int minDistance(string w1, string w2) {
if (w1.size() == 0 || w2.size() == 0) return w1.size() + w2.size();
vector<vector<int>> dp(w1.size(), vector<int>(w2.size(), 0));
for (int i = 0; i < w1.size(); ++i)
for (int j = 0; j < w2.size(); ++j)
dp[i][j] = min((i == 0 || j == 0 ? max(i, j) : dp[i - 1][j - 1]) + (w1[i] == w2[j] ? 0 : 2),
1 + min(i == 0 ? j + 1 : dp[i - 1][j], j == 0 ? i + 1 : dp[i][j - 1]));
return dp[w1.size() - 1][w2.size() - 1];
}
``````

2. BSF + Memo

``````int minDistance(string& w1, string& w2, int p1, int p2, vector<vector<int>>& dp) {
if (p1 == w1.size() || p2 == w2.size()) return w1.size() - p1 + w2.size() - p2;
return dp[p1][p2] != - 1 ? dp[p1][p2] : dp[p1][p2] =
min(w1[p1] == w2[p2] ? minDistance(w1, w2, p1 + 1, p2 + 1, dp) : INT_MAX,
1 + min(minDistance(w1, w2, p1 + 1, p2, dp), minDistance(w1, w2, p1, p2 + 1, dp)));
}
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), -1));
return minDistance(word1, word2, 0, 0, dp);
}
``````

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