题目

类型：动态规划

image.png

解题思路

  1. 最长公共子序列的兄弟题
    题目让我们计算将两个字符串变得相同的最少删除次数，那可以思考一下，最后这两个字符串会被删成什么样子？
    删除的结果不就是它俩的最长公共子序列嘛！
    那么，要计算删除的次数，就可以通过最长公共子序列的长度推导出来

int minDistance(String s1, String s2) {<br /> int m = s1.length(), n = s2.length();<br /> // 复用前文计算 lcs 长度的函数<br /> int lcs = longestCommonSubsequence(s1, s2);<br /> return m - lcs + n - lcs;<br />}

代码

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int m = word1.length();
  4.         int n = word2.length();
  5.         int[][] dp = new int[m+1][n+1];
  7.         for(int i = 1;i<=m;i++){
  8.             for(int j = 1;j<=n;j++){
  9.                 if(word1.charAt(i-1) == word2.charAt(j-1)){
  10.                     dp[i][j] = 1+ dp[i-1][j-1] ;
  11.                 }else{
  12.                     dp[i][j] = Math.max(dp[i-1][j] ,dp[i][j-1] )   ;
  14.                 }
  15.             }
  16.         }
  17.         return m-dp[m][n]+n-dp[m][n];
  18.     }
  19. }