本文共 2362 字，大约阅读时间需要 7 分钟。

题目：

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

The length of given words won’t exceed 500.

Characters in given words can only be lower-case letters.

解释：

可以对字符串执行删除字符操作，每次只能删除一个字符。最少需要多少步可以让两个字符串相等。 动态规划 与712. Minimum ASCII Delete Sum for Two Strings类似 dp[i][j]表示s1的前i个字符和s2的前j个字符所需要进行操作的最小值 其实这道题目也可以用lcs（subsequence）做，参考对lcs（subsequence的介绍） python代码：

class Solution(object):    def minDistance(self, word1, word2):        """        :type word1: str        :type word2: str        :rtype: int        """        def lcsubsequence(A, B):            m=len(A)            n=len(B)            dp=[[0]*(n+1) for _ in range(m+1)]            for i in range(1,m+1):                for j in range(1,n+1):                    if A[i-1]==B[j-1]:                        dp[i][j]=dp[i-1][j-1]+1                    else:                        dp[i][j]=max(dp[i][j-1],dp[i-1][j])            return dp[m][n]        m=len(word1)        n=len(word2)        if m==0 and n==0:            return 0        elif m==0:            return n        elif n==0:            return m        else:            return m+n-2*lcsubsequence(word1,word2)

c++代码：

class Solution {
   public:    int minDistance(string word1, string word2) {
           int m=word1.size(),n=word2.size();        if (m==0 && n==0)            return 0;        else if(m==0)            return n;        else if(n==0)            return m;        return m+n-2*lcsubsequence(word1,word2);    }    int lcsubsequence(string A,string B)    {
           int m=A.size();        int n=B.size();        vector
   
    
     > dp(m+1,vector
     
      (n+1,0));        for (int i=1;i<=m;i++)        {
               for(int j=1;j<=n;j++)            {
                   if (A[i-1]==B[j-1])                {
                       dp[i][j]=dp[i-1][j-1]+1;                }                else                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);                }        }        return dp[m][n];    }};
     
    
   

总结：

注意，如果求的是lcsubarray，则需要用一个maxLen来记录当前最长的子串的长度，如果求的是lcsubsequence，则不需要用maxLen，直接返回dp[m][n]即可，当然用maxLen记录也不错，因为最后一定会遍历到dp[m][n]的，只是比较大小和更新的时候会浪费时间。

转载地址：http://swmcn.baihongyu.com/