在算法面试的浩瀚星空中,“编辑距离”(Edit Distance)问题犹如一颗璀璨的星辰,以其深刻的数学背景和广泛的应用领域,成为了众多面试官青睐的考题之一。编辑距离,又称莱文斯坦距离(Levenshtein Distance),衡量的是将一个字符串转换成另一个字符串所需的最少编辑操作次数,这些编辑操作包括插入、删除和替换字符。它不仅在文本处理、生物信息学、拼写检查等领域有重要应用,也是评估字符串相似度的一种有效手段。
给定两个字符串s1
和s2
,要求计算它们之间的编辑距离。编辑距离定义为将s1
转换为s2
所需的最少单字符编辑(插入、删除或替换)次数。
解决编辑距离问题最经典且高效的方法是使用动态规划(Dynamic Programming, DP)。动态规划通过将原问题拆解为规模较小的子问题,并存储子问题的解来避免重复计算,从而优化整体性能。
设dp[i][j]
表示将s1
的前i
个字符转换为s2
的前j
个字符所需的最少编辑次数。注意,这里的“前i
个字符”和“前j
个字符”是包含索引i-1
和j-1
的字符在内的子串。
i=0
时,即s1
为空字符串,要将空字符串转换成s2
的前j
个字符,只能通过j
次插入操作,因此dp[0][j] = j
。j=0
时,dp[i][0] = i
,即将s1
的前i
个字符转换为空字符串,需要i
次删除操作。对于i > 0
且j > 0
的情况,我们需要考虑三种操作:
s1[i-1] == s2[j-1]
,则当前字符无需编辑,直接继承前一个状态的结果,即dp[i][j] = dp[i-1][j-1]
。s1
的第i
个位置插入一个与s2[j-1]
相同的字符,相当于将s1
的前i-1
个字符转换为s2
的前j
个字符,然后再添加一个字符(即插入操作),所以dp[i][j] = dp[i-1][j] + 1
。s1
的第i
个字符,相当于将s1
的前i-1
个字符转换为s2
的前j
个字符,因此dp[i][j] = dp[i][j-1] + 1
。综合以上三种情况,取最小值作为dp[i][j]
的值,即:
[
dp[i][j] = \min(dp[i-1][j-1] + (s1[i-1] \neq s2[j-1]), dp[i-1][j] + 1, dp[i][j-1] + 1)
]
按照上述状态转移方程,从dp[0][0]
开始,逐步填充整个dp
表,直到dp[m][n]
,其中m
和n
分别是s1
和s2
的长度。
最终,dp[m][n]
即为所求的编辑距离。
def minDistance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# 填表
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
cost = 0
else:
cost = 1
dp[i][j] = min(dp[i - 1][j - 1] + cost, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
return dp[m][n]
# 示例
s1 = "kitten"
s2 = "sitting"
print(minDistance(s1, s2)) # 输出: 3
虽然上述解法在时间和空间上都是高效的,但有时候面试中可能会要求进一步优化空间复杂度。观察状态转移方程,我们可以发现dp[i][j]
只依赖于其左边、上边和左上方的值,因此可以使用滚动数组或一维数组来优化空间复杂度至O(n)。
编辑距离在多个领域都有广泛的应用,包括但不限于:
编辑距离问题不仅考察了面试者对动态规划算法的理解和掌握程度,还考验了其对问题建模和优化的能力。通过深入理解编辑距离的原理和实现细节,我们可以更好地应对面试中的类似问题,并在实际项目中灵活运用这一强大的工具。