# Dynamic Programming and Memoization Solution

• DP:

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

Memoization

``````class Solution {
unordered_map<string, int> mem;
int match(const string &word1, const string &word2, int idx1, int idx2) {
auto id = to_string(idx1) + " " + to_string(idx2);
if (mem.count(id)) {
return mem[id];
} else if (idx2 == word2.size() || idx1 == word1.size()) {
return word1.size() - idx1 + word2.size() - idx2;
}
int subans = INT_MAX;
auto pos = word1.find(word2[idx2], idx1);
if (pos != string::npos) subans = pos - idx1 + match(word1, word2, pos + 1, idx2 + 1);
subans = min(subans, 1 + match(word1, word2, idx1, idx2 + 1));
return mem[id] = subans;
}
public:
int minDistance(string word1, string word2) {
return match(word1, word2, 0, 0);
}
};
``````

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