1. 插入：插入一个字符。
2. 删除：删除一个字符。
3. 替换：将一个字符替换为另一个字符。

下面我将用Python实现计算Levenshtein距离的几种常见方法,从最直观的递归方法到最高效的动态规划方法，并解释其原理。

递归实现（不推荐，仅用于理解）

这是最直观的实现方式,它直接模拟了距离的定义，对于一个字符串 s1 和 s2，我们可以考虑最后一个字符：

• s1 和 s2 的最后一个字符相同，那么距离就等于 s1[0:-1] 和 s2[0:-1] 的距离。
• 如果不同,我们需要进行一次操作，那么距离就是以下三种情况的最小值 + 1：
  • 替换：计算 s1[0:-1] 和 s2[0:-1] 的距离，然后加1（代表替换最后一个字符）。
  • 删除：计算 s1[0:-1] 和 s2 的距离，然后加1（代表从 s1 中删除最后一个字符）。
  • 插入：计算 s1 和 s2[0:-1] 的距离，然后加1（代表在 s1 末尾插入 s2 的最后一个字符）。

def levenshtein_recursive(s1, s2):
    """
    递归方式计算Levenshtein距离。
    这种方法非常慢，因为存在大量的重复计算，仅用于演示概念。
    """
    # 基本情况：如果一个字符串为空，距离就是另一个字符串的长度
    if len(s1) == 0:
        return len(s2)
    if len(s2) == 0:
        return len(s1)
    # 如果最后一个字符相同，则问题简化
    if s1[-1] == s2[-1]:
        return levenshtein_recursive(s1[:-1], s2[:-1])
    # 如果最后一个字符不同，考虑三种操作并取最小值
    # 替换
    replace_cost = levenshtein_recursive(s1[:-1], s2[:-1]) + 1
    # 删除
    delete_cost = levenshtein_recursive(s1[:-1], s2) + 1
    # 插入
    insert_cost = levenshtein_recursive(s1, s2[:-1]) + 1
    return min(replace_cost, delete_cost, insert_cost)
# --- 示例 ---
# s1 = "kitten"
# s2 = "sitting"
# print(f"递归结果: {levenshtein_recursive(s1, s2)}") # 输出: 3

缺点：时间复杂度为指数级 O(3^n)，对于稍长的字符串（比如超过20个字符）就会变得非常慢，因为它会重复计算很多子问题。

动态规划（推荐）

动态规划是解决Levenshtein距离的标准且最高效的方法,它通过一个二维表格（矩阵）来存储中间结果，从而避免了递归中的重复计算。

算法思想

1. 创建一个 (len(s1) + 1) x (len(s2) + 1) 的矩阵 dp。
2. dp[i][j] 将表示字符串 s1[0...i-1] 和 s2[0...j-1] 之间的Levenshtein距离。
3. 初始化：
   • 第一行 dp[0][j]：将一个空字符串 s1 变成 s2[0...j-1] 需要插入 j 个字符。dp[0][j] = j。
   • 第一列 dp[i][0]：将 s1[0...i-1] 变成一个空字符串 s2 需要删除 i 个字符。dp[i][0] = i。
4. 填充矩阵： 遍历矩阵，从 i=1 到 len(s1)，j=1 到 len(s2)：
   • s1[i-1] == s2[j-1]：当前字符匹配，不需要操作，距离等于左上角的值。dp[i][j] = dp[i-1][j-1]。
   • s1[i-1] != s2[j-1]：当前字符不匹配，需要进行一次操作，距离等于上方、左方、左上方三个值的最小值 + 1。
     • dp[i][j] = 1 + min(dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1]) # 替换
5. 结果：矩阵的右下角 dp[len(s1)][len(s2)] 就是最终的Levenshtein距离。

Python实现

def levenshtein_dp(s1, s2):
    """
    使用动态规划（二维矩阵）计算Levenshtein距离。
    这是标准且高效的实现方式。
    """
    m = len(s1)
    n = len(s2)
    # 创建一个 (m+1) x (n+1) 的矩阵，并用0初始化
    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]:
                # 字符相同，无需操作
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # 字符不同，取三种操作的最小值 + 1
                dp[i][j] = 1 + min(
                    dp[i - 1][j],    # 删除
                    dp[i][j - 1],    # 插入
                    dp[i - 1][j - 1]  # 替换
                )
    # 返回右下角的值，即最终距离
    return dp[m][n]
# --- 示例 ---
s1 = "kitten"
s2 = "sitting"
print(f"动态规划结果: {levenshtein_dp(s1, s2)}") # 输出: 3
s1 = "Sunday"
s2 = "Saturday"
print(f"动态规划结果: {levenshtein_dp(s1, s2)}") # 输出: 3

优点：时间复杂度为 O(mn)，空间复杂度也为 O(mn)，m 和 n 是两个字符串的长度，这对于大多数应用来说已经非常高效。

空间优化的动态规划

上面的方法使用了一个完整的二维矩阵,但实际上，在计算 dp[i][j] 时，我们只需要当前行、上一行和左上角的值，我们可以将空间复杂度优化到 O(min(m, n))。

Python实现

def levenshtein_optimized(s1, s2):
    """
    使用空间优化的动态规划计算Levenshtein距离。
    空间复杂度从 O(m*n) 优化到 O(min(m, n))。
    """
    # 为了节省空间，让 s2 是较长的字符串
    if len(s1) < len(s2):
        return levenshtein_optimized(s2, s1)
    # s1 是较长的字符串
    m, n = len(s1), len(s2)
    # 我们只需要两行：上一行 'prev' 和当前行 'curr'
    prev = list(range(n + 1))
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        # 初始化当前行的第一个元素
        curr[0] = i
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j],    # 删除 (对应 dp[i-1][j])
                                   curr[j - 1],  # 插入 (对应 dp[i][j-1])
                                   prev[j - 1])  # 替换 (对应 dp[i-1][j-1])
        # 完成当前行后，将其设置为上一行，为下一轮迭代做准备
        prev, curr = curr, prev
    # 循环结束后，结果在 'prev' 中，因为最后一步进行了 prev, curr = curr, prev
    return prev[n]
# --- 示例 ---
s1 = "kitten"
s2 = "sitting"
print(f"空间优化结果: {levenshtein_optimized(s1, s2)}") # 输出: 3

优点：与标准DP算法时间复杂度相同，但空间效率大大提高，尤其适用于处理非常长的字符串。

使用现成的库（实际开发首选）

在实际项目中,我们通常不需要自己实现这个算法，因为Python标准库和一些第三方库都提供了高度优化过的实现。

使用 thefuzz 库（推荐）

thefuzz (以前叫 fuzzywuzzy) 是一个非常流行的模糊字符串匹配库，它底层就使用了Levenshtein距离等算法。

首先需要安装：

pip install thefuzz

from thefuzz import fuzz
s1 = "kitten"
s2 = "sitting"
# fuzz.ratio 计算的是相似度百分比，基于编辑距离
# 我们可以根据需要推导出距离
similarity = fuzz.ratio(s1, s2) # 输出: 75
# 最大可能长度是 max(len(s1), len(s2)) = 7
# 相似度 = (1 - 距离 / max_len) * 100
# 75 = (1 - distance / 7) * 100  => distance / 7 = 0.25 => distance = 1.75
# 这个库对距离有更复杂的定义，所以直接 ratio 更常用。
# 如果需要精确的编辑距离，可以使用 Levenshtein 包

使用 python-Levenshtein 库

这是一个纯C实现的库,速度极快。

首先需要安装：

pip install python-Levenshtein

import Levenshtein
s1 = "kitten"
s2 = "sitting"
# 直接计算距离
distance = Levenshtein.distance(s1, s2)
print(f"python-Levenshtein 结果: {distance}") # 输出: 3
# 还可以计算其他指标，如相似度
ratio = Levenshtein.ratio(s1, s2)
print(f"python-Levenshtein ratio: {ratio}") # 输出: 0.75...

对于学习和面试,掌握方法二（动态规划）至关重要，对于生产环境，直接使用方法四（现成库）是最好的选择。