class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(),n = word2.size();
        int l = lcs(word1,word2,m,n);
        return m + n -2 * l;
    }
private:
    int lcs(string word1,string word2,int m,int n) {
        if(m == 0 || n == 0)  return 0;
        if(word1[m - 1] == word2[n - 1]) {
            return 1 + lcs(word1,word2,m - 1,n - 1);
        } else {
            return max(lcs(word1,word2,m-1,n),lcs(word1,word2,m,n-1));
        }
    }
};

使用lcs方法计算，如果存在最长公共子序列，那么两个字符串长度之和减去两份最长公共子序列长度，就是需要删除的次数，可惜的时程序执行Time Limit Exceeded，令人奇怪的时失败用例似乎并不复杂：

"dinitrophenylhydrazine"
"benzalphenylhydrazone"

尝试使用递归加记忆化方式，解决子问题重复计算的问题，上面失败的用例通过后，又会存在新的用例执行Time Limit Exceeded

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(),n = word2.size();
        vector<vector<int>> mem(m + 1,vector<int>(n + 1,0));
        
        return m + n - 2 * lcs(word1,word2,m,n,mem);
    }
private:
    int lcs(string word1,string word2,int m,int n,vector<vector<int>> &mem) {
        if(m == 0 || n ==0)  return 0;
        if(mem[m][n] > 0) return mem[m][n];
        
        if(word1[m - 1] == word2[n - 1]) {
            mem[m][n] = 1 + lcs(word1,word2,m - 1,n - 1,mem);
        } else {
            mem[m][n] = max(lcs(word1,word2,m-1,n,mem),lcs(word1,word2,m,n-1,mem));
        }
        
        return mem[m][n];
    }
};

失败的case:

Last executed input
"tzwcgoozzzqpwdyvsbh"
"bsjfnmllccynlxgzqhysewtacutpoengqqqyup"

上面的代码其实存在一个小的待改进点，如果将vector初始化时默认值设置为-1，针对dp[i][j]==0的场景我们是不需要重复计算的，调整后的代码：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(),n = word2.size();
        vector<vector<int>> mem(m+1,vector(n+1,-1));
        return m + n - 2*lcs(word1,word2,m,n,mem);
    }
private:
    int lcs(string word1,string word2,int m ,int n,vector<vector<int>> & mem) {
        if(m == 0 || n == 0)
            return 0;
        
        if(mem[m][n] >= 0)
            return mem[m][n];
        
        if(word1[m-1] == word2[n-1])
            mem[m][n] =  1 + lcs(word1,word2,m-1,n-1,mem);
        else
            mem[m][n] = max(lcs(word1,word2,m,n-1,mem),lcs(word1,word2,m-1,n,mem));
        
        return mem[m][n];
    }
};

运行结果：

Runtime: 648 ms, faster than 5.04% of C++ online submissions for Delete Operation for Two Strings.
Memory Usage: 328.2 MB, less than 5.04% of C++ online submissions for Delete Operation for Two Strings.

常规动态规划算法求解(AC)：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        //dp[i][j]表示word1[0---i]和word2[0---j]中最长公共子序列
        vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(word1[i - 1] == word2[j - 1]) 
                    dp[i][j] = 1 + dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

        return m+n-2*dp[m][n];
    }
};