动态规划之编辑距离系列

发表于   |   分类于 ，

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

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

编辑距离

编辑距离题目描述

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

定义状态

同时遍历word1和word2，i指针遍历word1，j指针遍历word2。

我们定义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
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] 和 dp[0][j]
  // 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 为结尾的 t[: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;
}