This problem is the same as finding the longest common subsequence of two strings.
Solution 1 (Recursion, TLE)
class Solution {
public:
int minDistance(string word1, string word2) {
int commonLen = LCS(word1, word2);
int n = word1.length();
int m = word2.length();
return n + m - 2*commonLen;
}
int LCS(string s1, string s2) {
if(s1.empty() || s2.empty()) return 0;
int n = s1.length();
int m = s2.length();
if(s1[n-1] == s2[m-1]) return 1 + LCS(s1.substr(0, n-1), s2.substr(0, m-1));
else return max(LCS(s1.substr(0, n-1), s2), LCS(s1, s2.substr(0, m-1)));
}
};
This solution is TLE. Not sure if the algorithm is wrong.
update
The algorithm is correct, but it does not have the memorization part, so it basically requires computing the subproblem repeatedly, thus results in TLE.
Solution 2 (DP with memorization)
class Solution {
public:
int minDistance(string word1, string word2) {
int commonLen = LCS(word1, word2);
int n = word1.length();
int m = word2.length();
return n + m - 2*commonLen;
}
int LCS(string s1, string s2) {
int n = s1.length();
int m = s2.length();
vector<vector<int>> res(n+1, vector<int>(m+1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(s1[i-1] == s2[j-1]) res[i][j] = 1 + res[i-1][j-1];
else res[i][j] = max(res[i-1][j], res[i][j-1]);
}
}
return res[n][m];
}
};
Same idea as the recursive solution, but this one is accepted.
