1652674511(1).png

思路

题意很清晰，就是求最长公共子序列，在用两个字符串总长减去2最长
*我发现我有一个毛病！不认真审题就开始做，还容易被给的样例给带跑偏。
比如这道题，我一开始因为样例以为是 公共【连续】子序列，但其实题目中有一句话：
每步 可以删除任意一个字符串中的一个字符。
我没看，但这句话表示是不需要连续的。

  1. var minDistance = function(word1, word2) {
  2.     // 转换题意，求最长公共子序列长度，再用总长度减去它
  3.     let dp =new Array(word1.length+1).fill(0).map(()=>new Array(word2.length+1).fill(0))
  4.     -----学一下下面这种写法，简单点
  5.     let dp = Array.from(Array(s.length + 1), () => Array(t.length +1).fill(0));
  6.     let result =0
  7.     for(let i=1;i<=word1.length;i++){
  8.         for(let j=1;j<=word2.length;j++){
  9.             if(word1[i-1]===word2[j-1]){
  10.                 dp[i][j] =dp[i-1][j-1] +1
  11.             }else{
  12.                 dp[i][j] =Math.max(dp[i-1][j],dp[i][j-1])
  13.             }
  14.             result =Math.max(result,dp[i][j])
  15.         }
  16.     }
  17.     return word1.length+word2.length -2*result
  18. };