动态规划之编辑距离系列

发表于   |   分类于 ，

编辑距离是动态规划经典题之一。编辑距离是指给定两个字符串，计算由其中一个字符串通过添加，修改，删除字符操作后转变为另一个字符串所需的最少操作数。

同样，由编辑距离也延伸出来一些变种题目解题思路也是类似，今天就来整理一下这个系列，做个备忘录，方便学习。

编辑距离

编辑距离题目描述

对于编辑距离这个题目而言，我们最终并不关心两个字符串经过如何的编辑得到一致，而只关心最终的操作步骤数即可。这也是很多动态规划题目的解决场景，不关心具体步骤，只关心最终状态。

定义状态

我们定义dp[i][j]为字符串word1以i-1为结尾的的子串word1[:i-1]和字符串word2以j-1为结尾的子串word[:j-1]的最短编辑距离，那么最终要求的结果便是 dp[word1.length][word2.length]。

那么，对于 word1[i-1] 和 word2[j-1] 比较，有两种情况：

  • word1[i-1]==word2[j-1]，遇到相同的元素，说明不需要编辑，即 dp[i][j]=dp[i-1][j-1]
  • word1[i-1]!=word2[j-1]，遇到了不同的元素，此时需要编辑操作
    • 删除word1一个元素word1[i-1]，那么就是以i-2为结尾的word1子串word1[:i-2]与j-1为结尾的word2的子串word2[:j-1]的最短编辑距离再加上一个操作。即 dp[i][j]=dp[i-1][j]+1。
    • 删除word2一个元素word2[j-1]，那么就是以j-2为结尾的word2子串word2[:j-2]与i-1为结尾的word1的子串word1[:i-1]的最短编辑距离再加上一个操作，即 dp[i][j]=dp[i][j-1]+1
    • 替换word1的word1[i-1]为word2的word2[j-1]或者替换word2[j-1]为word1[i-1]。一个替换操作之后，相当于 word1[i-1]==word2[j-1]，即最终 dp[i][j]=dp[i-1][j-1]+1
    • 最终取三者最小即可

上面两个都是删除操作，为什么不是添加操作呢？其实对word1进行删除操作就相当于对word2进行添加操作，同理，对word2进行删除操作就相当于对word1进行添加操作。

状态转移方程：

1
2
3
         |- dp[i-1][j-1]，word1[i-1]==word2[j-1]
dp[i][j]=|
         |- min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1，word1[i-1]!=word2[j-1]

初始化状态

对于 dp[i][0]，相当于word2为空字符串，将word1转换为空字符串需要删除i个字符，即 dp[i][0]=i
对于 dp[0][j]，相当于word1为空字符串，将word2转换为空字符串需要删除j个字符，即 dp[0][j]=j

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function minDistance(word1: string, word2: string): number {
  const [l1, l2] = [word1.length, word2.length];
  const dp = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0));
  // dp[i][0]: word2为空字符串，word1要删除i个字符才能与空字符串相等
  for (let row = 1; row < l1; row++) {
    dp[row][0] = row;
  }
  // dp[0][j]：同理，word1为空字符串，word2要删除j个字符才能与空字符串相等
  for (let col = 1; col < l2; col++) {
    dp[0][col] = col;
  }
  for (let row = 1; row < l1 + 1; row++) {
    const char1 = word1[row - 1];
    for (let col = 1; col < l2 + 1; col++) {
      const char2 = word2[col - 1];
      if (char1 == char2) {
        dp[row][col] = dp[row - 1][col - 1];
      } else {
        dp[row][col] = Math.min(
          dp[row - 1][col - 1],
          dp[row - 1][col],
          dp[row][col - 1]
        ) + 1;
      }
    }
  }
  return dp[l1][l2];
};

两个字符串的删除操作

两个字符串的删除操作

本题可以说是编辑距离的一个简化版本，对于两个字符串的操作仅限于删除字符，求最终的删除距离。

状态定义

和编辑距离一样，我们定义 dp[i][j] 为 word1中以i-1为结尾的子串word1[:i-1]和word2中以j-1为结尾的子串word2[:j-1]要达到相等所需要删除的最小操作数。

我们定义 dp[i][j] 为 word1中以i-1为结尾的子串word1[:i-1]和word2中以j-1为结尾的子串word2[:j-1]要达到相等所需要删除的最小操作数。

那么，对于word1[i-1]和word2[j-1]而言有两种情况：

  1. word1[i-1]==word2[j-1]，此时说明遇到相同元素，则说明word1[i-1]和word2[j-1]都不用删除，最小操作数dp[i][j]直接等于dp[i-1][j-1]，即直接在子串word1[:i-2]和word2[:j-2]中操作即可
  2. word1[i-1]!=word2[j-1]，此时有三种情况：
    1. 两次删除操作，删除word1[i-1]和word2[j-1]，此时 dp[i][j]=dp[i-1][j-1]+2
    2. 一次删除操作，删除word1[i-1]，此时 dp[i][j]=dp[i-1][j]+1
    3. 一次删除操作，删除word2[j-1]，此时dp[i][j]=dp[i][j-1]+1
    4. 三种情况中取最小的一个，即 dp[i][j]=min(dp[i-1][j-1]+2, dp[i][j]=dp[i-1][j]+1, dp[i][j]=dp[i][j-1]+1)

最终的状态转移公式：

1
2
3
         |- dp[i-1][j-1]，word1[i-1]==word2[j-1]
dp[i][j]=|
         |- min(dp[i-1][j-1]+2, dp[i-1][j]+1, dp[i][j-1]+1)，word1[i-1]!=word2[j-1]

初始化状态

对于dp[i][0]表示word2为空串，字符串word1要删除i个字符才能与空字符串相等，因此dp[i][0]要初始化成i。
对于dp[0][j]表示word1为空串，字符串word2要删除j个字符才能与空字符串相等，因此dp[0][j]要初始化成j。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function minDistance(word1: string, word2: string): number {
  const [l1, l2] = [word1.length, word2.length];

  const dp = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0));
  
  // 初始化状态
  // dp[i][0]: word2为空字符串，word1要删除i个字符才能与空字符串相等
  for (let i = 0; i <= l1; i++) {
    dp[i][0] = i;
  }
  // dp[0][j]：同理，word1为空字符串，word2要删除j个字符才能与空字符串相等
  for (let j = 0; j <= l2; j++) {
    dp[0][j] = j;
  }
  
  for (let i = 1; i <= l1; i++) {
    for (let j = 1; j <= l2; j++) {
      if (word1[i - 1] == word2[j - 1]) {
        // 两个位置字符相等，说明不必删除，删除次数直接等于 dp[i-1][j-1]
        dp[i][j] = dp[i-1][j-1];
      } else {
        dp[i][j] = Math.min(
          dp[i-1][j-1] + 2, // 同时删除两个字符
          dp[i-1][j] + 1, // 只删除word1的字符word1[i-1]
          dp[i][j-1] + 1 // 只删除word2的字符word2[j-1]
        );
      }
    }
  }
  
  return dp[l1][l2];
}

不同的子序列

不同的子序列

本题要求s中有多少子序列包含t，其实就相当于是对s做多少删除操作能够得到t，也算是编辑距离，或者说上面两个字符串的删除题目的简化版。

状态定义

我们定义 dp[i][j] 为字符串s中以i-1为结尾的子串s[:i-1]中出现以j-1为结尾的tt[:j-1]的个数，那么最终要求的结果便是 dp[s.length][t.length]

我们定义 s[:i-1] 表示以i-1为结尾的s的子串，t[:j-1] 表示以j-1为结尾的t的子串

对于 s[i-1] 和 t[j-1] 有两种情况：

  1. s[i-1]==t[j-1]
    1. 当两者相等时，dp[i][j] 有两部分组成：
    2. 一部分是直接用 s[:i-1] 来匹配 t[:j-1]，这种情况下由于 s[i-1]==t[j-1]，因此个数等于dp[i-1][j-1]
    3. 一部分是s[:i-1]子串删除字符s[i-1]来匹配t[:j-1]，这种情况下，个数为dp[i-1][j]
    4. 为什么删除s[i-1]而不删除t[j-1]，因为我们要做的是对s做删除操作得到t
  2. s[i-1]!=t[j-1]
    1. 当两者不相等时，dp[i][j] 只有一部分组成，相当于s[:i-1]直接删除s[i-1]来匹配，个数为 dp[i-1][j]

所以最终的状态转移公式为：

1
2
3
            |--- dp[i-1][j-1]+dp[i-1][j]， s[i-1]==t[j-1]
dp[i][j] =  |
            |--- dp[i-1][j]， s[i-1]!=t[j-1]

初始化状态

我们将 dp[i][0] 都初始化为1，将 dp[0][j] 都初始化为0。
对于 dp[i][0] 表示的是s的任意子串如何操作得到空串t，那肯定是删除全部的字符得到空串，只有这一种方法，因此初始化为1。
对于 dp[0][j] 表示空串s如何做删除操作得到长度为j的字符串t，这种情况无论如何也不能通过删除操作得到，因此初始化为0。
注意两者有一个交集dp[0][0]，设置为1。因为空串可以不做任何操作就可以得到空串。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function numDistinct(s: string, t: string): number {
  const [ls, lt] = [s.length, t.length];
  const dp = new Array(ls + 1).fill(0).map(() => new Array(lt+1).fill(0));
  
  // 初始化状态
  for (let i = 0; i <= ls; i++) {
    dp[i][0] = 1;
  }
  
  for (let i = 1; i <= ls; i++) {
    const idxs = i - 1;
    for (let j = 1; j <= lt; j++) {
      const idxt = j - 1;
      if (s[idxs] == t[idxt]) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }

  return dp[ls][lt];
};

最长公共子序列

最长公共子序列

最长公共子序列，也可以算是编辑距离延伸出来的一道题。要求两个字符串的最长公共子序列，可以认为是对两个字符串进行删除不同元素操作，然后留下最长的公共子序列。

定义状态

我们定义状态 dp[i][j] 表示text1中以i-1为结尾的子串text1[:i-1]与text2中以j-1为结尾的子串text2[:j-1]的最长公共子序列长度。
对于 text1[i-1] 和 text2[j-1] 比较，有两种情况：

  • text1[i-1]==text2[j-1]，如果两者相同，相当于找到了相同元素，那么 dp[i][j]=dp[i-1][j-1]+1
  • text1[i-1]!=text2[j-1]，两者不同，那么我们可以找 text1[:i-2]与text2[:j-1]的最长公共子序列长度和 text[:i-1]与text2[:j-2]的最长公共子序列的长度，取最大的。

因此，状态转移方程如下：

1
2
3
            |-- dp[i-1][j-1]+1, text1[i-1]==text2[j-1]
dp[i][j] =  |
            |-- max(dp[i-][j-1],dp[i-1][j], dp[i][j-1])，text1[i-1]!=text2[j-1]

初始化状态

我们初始化 dp[i][0] 和 dp[0][j] 都为0，因为dp[i][0]和dp[0][j]可认为是空格与其他字符串的最长公共子序列长度，空格与任意字符串的最长公共子序列都是0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function longestCommonSubsequence(text1: string, text2: string): number {
  const [l1, l2] = [text1.length, text2.length];
  const dp = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0));

  for (let i = 1; i <= l1; i++) {
    for (let j = 1; j <= l2; j++) {
      if (text1[i-1] == text2[j-1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[l1][l2];
};

判断子序列

判断子序列

双指针

本题一般会使用双指针解决，而且双指针也是解决本题一种高效的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 双指针
function isSubsequence(s: string, t: string): boolean {
  const [ls, lt] = [s.length, t.length];

  let [ps, pt] = [0, 0];

  while (pt <= lt) {
    if (ps == ls) {
      return true;
    }
    if (pt == lt) {
      return false;
    }
    if (s[ps] == t[pt]) {
      ps++;
    }
    pt++;
  }
  return false;
};

但除此之外，还可以用动态规划的思路来解决，而且与编辑距离还是有点关系。

动态规划

要判断s是否是t的子序列，相当于判断s和t的最长公共子序列长度是否等于s的长度，如果最长公共子序列长度等于s的长度，那么说明整个s便是t的一个子序列。这样就和上面的 【最长公共子序列】是一道题了。

具体的状态考定义和状态转移方程是一样的，可以参考上题，唯一不同点在于返回值，需要判断一下长度是否相等即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isSubsequence2(s: string, t: string): boolean { 
  const [ls, lt] = [s.length, t.length];
  const dp = new Array(ls + 1).fill(0).map(() => new Array(lt+1).fill(0));
  
  for (let i = 1; i <= ls; i++) {
    for (let j = 1; j <= lt; 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]);
      }
    }
  }
  return dp[ls][lt] == ls;
}

除了上面这几个和编辑距离相关的字符串的题目之外，其实还有一些数组的题目，其解题思路也和编辑距离类似。
数组也会有子序列，子数组的概念，所以这里一并把几个与数组相关的类似的题目整理一下。

最长重复子数组

最长重复子数组

本题和上面【最长公共子序列】类似，可以说是其一个变种题。

定义状态

本题要求两个数组的最长连续子数组，而子数组为一个数组的连续切片，即占据连续的位置。比如数组 [1,2,3,2,1]， 其中 [1,2,3]是其一个子数组，而 [1,3,2] 不是其子数组，而只能算其子序列。

由于子数组占据连续的位置，因此我们定义状态 dp[i][j] 表示以 nums1[i-1] 为结尾的子数组和以 nums2[j-1] 为结尾的子数组的最长重复子数组长度。
那么整个题目的解便是dp的最大值。

对于 nums1[i] 和 nums2[j] 相比较，有两种情况：

  • nums1[i]==nums2[j]: 两者相等，说明遇到相同的元素，那么 dp[i][j]=dp[i-1][j-1]+1
  • nums1[i]!=nums2[j]: 两者不相登，那么以两者作为结尾的子数组必然不会相等，长度为0，即 dp[i][j]=0

最终的状态转移方程是：

1
2
3
           |- dp[i-1][j-1] + 1, nums1[i-1]==nums2[j-1]
dp[i][j] = |
           |- 0， nums1[i-1]!=nums2[j-1]

初始化状态

根据状态的定义，dp[i][j] 表示以 nums1[i-1] 为结尾的子数组和以 nums2[j-1] 为结尾的子数组的最长重复子数组长度，那么对于 dp[0][j] 和 dp[i][0] 而言，相当于是 nums1 为空和 nums2 为空的两种情况，所以默认都初始化先为0。即 dp[0][j]=0, dp[i][0]=0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findLength(nums1: number[], nums2: number[]): number {
  const [l1, l2] = [nums1.length, nums2.length];
  // 定义 dp[i][j] 为以nums1[i]为结尾的子数组和以nums2[j]为结尾的子数组的最长重复子数组长度
  const dp = new Array(l1 + 1).fill(0).map(() => new Array(l2 + 1).fill(0));
  // 记录最大dp值
  let max = 0;
  
  for (let i = 1; i <= l1; i++) {
    for (let j = 1; j <= l2; j++) {
      if (nums1[i-1] == nums2[j-1]) {
        // 遇到相同的，其结果为左上角格子加1
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        // 否则设置dp[i][j]为0
        dp[i][j] = 0;
      }
      
      max = Math.max(max, dp[i][j]);
    }
  }

  return max;
};