编辑距离类问题

判断子序列

https://leetcode.cn/problems/is-subsequence/description/

图 6

思路
这题和之前的最长公共子序列有什么关系呢？
关系在于，这题的最长公共子序列长度和S1的长度相等说明有关系。

这也是编辑距离的入门题目，下面是编辑距离的基本思路

1、二维dp数组，dp[i][j]，以i-1结尾的s1和以j-1结尾的s2的最长公共子序列。
2、递推公式：
- if (s1[i-1]==s2[i-2]) dp[i-1][j-1]+1;
- else dp[i][j] = max(dp[i-1][j],dp[i][j-1])
3、初始化：均为0
4、遍历顺序：

var isSubsequence = function(s, t) {
  let n = s.length
  let m = t.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + 1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  if (dp[n][m] == n) return true
  return false
};

不同的子序列

https://leetcode.cn/problems/distinct-subsequences/description/

图 3

思路
这道题目如果不是子序列，而是要求连续序列的，那就可以考虑用KMP。

这道题目相对于72. 编辑距离，简单了不少，因为本题相当于只有删除操作，不用考虑替换增加之类的。

这道题可以理解为怎么删除元素可以由s变为t；

1、二维dp数组，dp[i][j]以i-1为结尾的s中以j-1为结尾的t的个数
2、递推公式：
- if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] +dp[i-1][j],使用s[i-1]这个元素+不使用s[i-1]这个元素
- else dp[i][j] = dp[i-1][j],模拟删除当前元素，也就是不考录当前的元素。
3、初始化：
- dp[i][0] = 1(); t是空字符串的话，把s中元素全部删除可以得到t
- dp[0][j] = 0; s为空字符串，t不可能出现在s中，所以未0
- dp[0][0]= 1; s和t都为空字符串的话，只有一种可能
4、遍历顺序：

var numDistinct = function(s, t) {
  let n = s.length
  let m = t.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=0;i<=n;i++) {dp[i][0]=1}
  for (let i=1;i<=n;i++){
    for (let j=1;j<=m;j++){
      //相等，可以选择使用s[i-1]或者不使用s[i-1]
      if (s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
      else dp[i][j] = dp[i-1][j]  //不相等说明s[i-1]用不了得删掉。
    }
  }
  return dp[n][m]
};

两个字符串的删除操作

https://leetcode.cn/problems/delete-operation-for-two-strings/description/

图 4

思路1
求出最长公共子序列，然后用n+m-2x，n,m,s分别表示字符串1、字符串2和最长公共子字符串的长度。

var minDistance = function(word1, word2) {
  let n = word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
      else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  }
  return n+m-2*dp[n][m]
};

思路2

1、二维dp数组，dp[i][j]以i-1为结尾的word1和以j-1为结尾的word2相同需要的最少操作。
2、递推公式：始终记得dp数组的含义
- if (word1[i-1] == word2[i-1]) dp[i][j] = dp[i-1][j-1]，如果相等说明不需要操作。
- else dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)
- 由于dp[i][j-1]= dp[i-1][j-1]+1
3、初始化：dp[i][0] = i,dp[0][j] = j,dp[0][0] = 0
遍历顺序：

var minDistance = function(word1, word2) {
  let n = word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  //这两个for循环用于初始化dp数组
  for (let i=0;i<=n;i++){
    dp[i][0] = i
  }
  for (let j=0;j<=m;j++){
    dp[0][j] = j
  }
  for (let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]
      else dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1)
    }
  }
  return dp[n][m]
};

编辑距离

https://leetcode.cn/problems/edit-distance/description/

图 5

思路
看起来好复杂哦。

题目要求讲word1转为word2的最少操作次数，但实际上我们可以从word2转为word3，或者word1和word2同时操作都可以

1、dp[i][j]：以i-1为结尾的word1和j-1为结尾的word2的最少的操作次数

2、递推公式：

if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1],相同不需要操作

else dp[i][j] = min(dp[i][j-1] + 1,dp[i-1][j]+1,dp[i-1][j-1]+1)

上操作了
增：word2[i-1]增加一个字符, dp[i][j] = dp[i][j-1] + 1
删：删掉word1[i-1] ,dp[i][j] = dp[i-1][j]+1
替换：dp[i][j] = dp[i-1][j-1]+1
eg: word1 = ‘ab’ , word2 = ‘a’ , 可以是ab删掉b，也可以a增加b。dp数组如下图所示意的：

a d

  +-----+-----+             +-----+-----+-----+
  |  0  |  1  |             |  0  |  1  |  2  |
  +-----+-----+   ===>      +-----+-----+-----+
a |  1  |  0  |           a |  1  |  0  |  1  |
  +-----+-----+             +-----+-----+-----+
d |  2  |  1  |
  +-----+-----+

3、初始化：
- dp[i][0] = i
- dp[0][j] = j
4、遍历顺序：

var minDistance = function(word1, word2) {
  let n= word1.length
  let m = word2.length
  let dp = Array.from({length:n+1},()=>Array(m+1).fill(0))
  for (let i=0;i<=n;i++){
    dp[i][0] = i
  }
  for (let j=0;j<=m;j++){
    dp[0][j] = j
  }
  for (let i=1;i<=n;i++){
    for (let j=1;j<=m;j++){
      if (word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1]
      else dp[i][j] = Math.min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1)
    }
  }
  return dp[n][m]
};