题目描述

官方描述(中文)
2021/09/25每日一题

思路

删除最少的字符,其实就是要剩余的字符尽量的多,要做到剩余的字符尽量的多,其实就是求取两个字符串的最长相同子序列。
两个字符串的最长相同子序列的求取肯定就用到动态规划。
首先新建一个二维数组dp,其中dp中i+1,j+1位置存储的是word1[0, i]和word2[0, j]的最长相同子序列。其中dp[i+1][j+1]可以dp[i][j],dp[i+1][j],dp[i][j+1]获得。存在两种情况。

  1. 如果word[i]==word2[j],dp[i+1][j+1]就等于dp[i][j]+1;
  2. 如果word[i]!=word2[j],dp[i+1][j+1]就是dp[i+1][j]与dp[i][j+1]中的较大的值。
  3. 最后dp[word1.length()][word2.length()]就是两个字符串的最长相同子序列的长度。

代码

class Solution 
{
public:
    int minDistance(string word1, string word2) 
    {
        vector<vector<int>>dp(word1.length()+1, vector<int>(word2.length()+1,0));
        for(int i = 0; i< word1.length(); ++i)
        {
            for(int j = 0; j<word2.length(); ++j)
            {
                dp[i+1][j+1] = max(dp[i][j]+(word1[i]==word2[j]), max(dp[i][j+1],dp[i+1][j]));
            }
        }
        return word1.length()+word2.length()-dp[word1.length()][word2.length()]*2;
    }
};

运行结果

image.png

Q.E.D.