Edit Distance
LeetCode #72 · Medium · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Top-Down Dynamic Programming (Memoization)
Strategy
- 1Define a helper function that takes the current lengths of the two
- 2Base cases:
- 3Recursive step:
- 4Use a hash map to memoize results for state (n, m) to avoid
Time
O(n * m)
Space
O(n * m)
the recursion stack and hash map
Problem description(from LeetCode)
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: - Insert a character - Delete a character - Replace a character
Examples
Example 1
- Input:
- word1 = "horse", word2 = "ros"
- Output:
- 3
- Note:
- horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
Constraints
- •0 <= word1.length, word2.length <= 500
- •word1 and word2 consist of lowercase English letters.
C++ Solution
solution.cpp
struct pair_hash {
size_t operator()(const pair<int, int> &p) const {
return (long long)p.first << 32 ^ p.second;
}
};
class Solution {
public:
unordered_map<pair<int, int>, int, pair_hash> mp;
int minDistance(string word1, string word2) {
return helper(word1, word2, word1.length(), word2.length());
}
int helper(string &s, string &t, int n, int m) {
pair<int, int> key = {n, m};
if (mp.find(key) != mp.end()) return mp[key];
if (n == 0) return m;
if (m == 0) return n;
if (s[n - 1] == t[m - 1]) return mp[key] = helper(s, t, n - 1, m - 1);
return mp[key] =
1 + min(helper(s, t, n - 1, m),
min(helper(s, t, n, m - 1), helper(s, t, n - 1, m - 1)));
}
};