基本概念

• 编辑距离问题:
  • 编辑距离问题困难,解法却是很漂亮,而且也是少有的比较实用的算法
• 编辑距离使用场景:
  • 对于修改文章的错位内容.限制文章只能修改20个字,且支持增,删,替换操作,求修改的最优方案
  • 对于衡量DNA的相似程度 .DNA序列是由A, G, C, T组成的序列,可以类比成字符串,可以通过编辑距离衡量两个DNA序列的相似度,编辑距离越小,说明这两个DNA序列越相似

思路分析

• 编辑距离问题:
  • 给定两个字符串s1和s2, 只能使用3种操作,将s1变成s2, 求最小的操作数
  • 需要保证,不管是将s1变成s2, 还是将s2变成s1, 结果都要是一样的
• 在最长公共子序列中,解决两个字符串的动态规划问题,一般是使用两个指针i,j分别指向两个字符串的最后,然后一步一步向前走,缩小问题的规模
• 计算编辑距离:
  • 算法的base case:
    • s1和s2字符相同时.为了使编辑距离最小,不需要进行任务操作,直接移动即可
    • 如果j走完s2,i还没有走完s1. 为了使编辑距离最小,只能使用删除操作将s1缩短为s2
    • 如果i走完s1,j还没有走完s2, 为了使编辑距离最小,只能使用插入操作将s1增长为s2

问题解法

• 算法的base case: i走完s1或者j走完s2, 可以直接返回另一个字符串剩下的长度
• 对于每一对s1[i] 和s2[j] 有4种操作:

if s1[i] == s2[j]:
	不做操作,直接跳过skip
	i,j同时向前移动
else:
	操作 3 选 1:
		插入-insert
		删除-delete
		替换-replace
复制代码

• 对于3选1的操作,可以使用递归技巧,将3个操作全试一遍,然后根据哪个操作得到的编辑距离最小,就选择哪一个操作的结果

def minDistance(s1, s2) -> int:

	# 返回s1[0,..., i]和s2[0, ..., j]的最小编辑距离
	def dp(i, j):
		# base case
		if i == -1: return j + 1 
		if j == -1: return i + 1

		if s1[i] == s2[j]:
			# 不需要进行任务操作
				# s1[0,..., i]和s2[0, ..., j]的最小编辑距离等于s1[0,..., i - 1]和s2[0, ..., j - 1]的最小编辑距离
				# 即dp(i, j)等于dp(i - 1, j - 1) 
			return dp(i - 1, j - 1)
		else:
			return min(
				# 插入
					# 在s1[i]中插入1个和s2[j]一样的字符就可以匹配
					# 将s2的字符前移1位,继续比对
					# 插入操作,操作数加1
				dp(i, j - 1) + 1
				# 删除
					# 将s1[i]中删除这1个字符就可以匹配
					# 将s2的字符前移1位,继续比对
					# 删除操作,操作数加1
				dp(i - 1, j) + 1
				# 替换
					# 将s1[i]替换成s2[j]就可以继续匹配
					# 同时i,j前移1位,继续比对
					# 替换操作,操作数加1
				dp(i - 1, j - 1) + 1
			)
	return dp(len(s1) - 1, len(s2) - 1)
复制代码

• 该解法存在重叠子问题,需要通过动态规划算法进行优化

• 如何判断是否存在重叠子问题?
  • 抽象出解法的算法框架
  • 判断子问题到原问题的不同路径
  • 一旦存在重复的路径,就说明存在巨量的重复路径,也就是存在重叠子问题

问题优化

• 重叠子问题使用动态规划优化的方式有两种:
  • 备忘录
  • DP Table

备忘录

def minDistance(s1, s2) -> int:

# 备忘录
memo = dict()
def dp(i, j):
	if (i, j) in memo:
		return memo[(i, j)]
	...
	if s[i] == s[j]:
		memo[(i, j)] = ...
	else:
		memo[(i, j)] = ...
	return memo[(i, j)]
return dp(len(s1) - 1, len(s2) - 1)
复制代码

DP Table

• 首先需要理解DP数组的含义 ,DP数组是一个二维数组
  • base case: dp[...][0]和dp[0][...]
  • dp[i][j]的含义:
    • def dp(i, j) -> int: 返回s1[0,...,i] 和s2[0,...,j] 的最小编辑距离
    • dp[i - 1][j - 1]: 存储s1[0,...,i] 和s2[0,...j] 的最小编辑距离. 因为dp函数的i,j的值为 -1, 而数组的最小索引值为0. 所以DP数组会偏移一位

int minDistance(String s1, String s2) {
	int m = s1.length(), n = s2.length();
	int[][] dp = new int[m][n];
	// base case
	for (int i = 1; i <=m; i++) {
		dp[i][0] = i;
	}
	for (int j = 1; j <= n; j++) {
		dp[0][j] = j;
	}
	// 自底向上计算DP Table
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (s1.isCharAt(i) == s2.isCharAt(j)) {
				dp[i][j] = dp[i - 1][j - 1];
			} else {
				dp = min(
					// 删除
					dp[i - 1][j] + 1;
					// 替换
					dp[i - 1][j - 1] + 1;
					// 插入
					dp[i][j - 1] + 1;
				);
			}
		}
	}
	// 存储s1和s2的最小编辑距离
	return dp[m][n];
}

int min(int a, int b, int c) {
	return Math.min(a, Math.min(b, c));
}
复制代码

总结

• 处理两个字符串的动态规划问题:
  • 按照编辑距离的算法进行求解
  • 建立DP Table. 这样比较容易找出状态转移关系
• 因为每一个dp[i][j]只和附近的三个状态有关,所以空间复杂度可以压缩成O(min(m,n)),其中m,n是两个字符串的长度O(min(m,n)),其中m,n是两个字符串的长度
• 可以给DP Table中增加额外的信息:

Node[][] dp;

class Node {
	// 之前dp数组的数值
	int val;
	// 属性操作
	int choice;
}
复制代码

• 在做最优选择时,将操作记录下来,然后就可以从结果反推具体操作
• 最终结果是dp[m][n], 这里的val存在着最小编辑距离 ,choice存在着最后一个操作
• 重复此过程,可以一步一步回到起点dp[0][0], 形成一条路径,按这条路径进行字符串的编辑,就是最小编辑距离

• 最小编辑距离Java实现
• 最小编辑距离C++实现:

class DynamicProgramming {
	public:
		int minDistance(String s1, String s2) {
			int m = s1.size(), n = s2.size();
			vector<vector<int>> dp(m + 1, vector<int>(n + 1));
			// basecase
			// 当字符串s2为空时,字符串s1需要删除所有字符才能和s2相同
			for (int i = 1; i <= m; i++) {
				dp[i][0] = i;
			}
			// 当字符串s1为空时,字符串s2需要删除所有字符才能和s1相同
			for (int j = 1; j <= n; j++) {
				dp[0][j] = j;
			}
			// 自底向上求解
			for (int i = 1; i <= m; i++) {
				for (int j = 1; j <= n; j++) {
					if (s1[i - 1] == s2[j - 1]) {
						// 两个字符串当前的字符相等
						dp[i][j] = dp[i - 1][j - 1];
					} else {
						// 两个字符串当前的字符不相同
						dp[i][j] = min({
							// 删除s1[i]这个字符
							dp[i - 1][j] + 1,
							// 在s1[i]字符后面添加一个与s2[j]相同的字符
							dp[i][j - 1] + 1,
							// 将s1[i]的字符替换为s2[j]的字符
							dp[i - 1][j - 1] + 1
							});
					}
				}
			}
			// 储存整个s1和s2的最小编辑距离
			return dp[m][n];
		}
};