编辑距离（Levenshtein Distance）是度量两个字符串差异程度的基础指标，定义为将一个字符串变成另一个字符串所需的最少单字符编辑操作次数。允许的操作通常包括插入一个字符、删除一个字符以及替换一个字符。它在自然语言处理、拼写纠错、DNA序列比对以及版本差异对比中都有广泛应用。理解编辑距离不仅有助于解决实际工程中的相似度判断问题，也是学习动态规划思想的经典入口。
一、编辑距离的问题定义
给定两个字符串 s1 和 s2，长度分别为 m 和 n。我们希望通过一系列基本操作把 s1 转换成 s2，操作次数越少越好。每一次操作可以是：在 s1 中插入一个字符，使长度加一；从 s1 中删除一个字符，使长度减一；或者把 s1 当前某个位置的字符替换成另一个字符。这三种操作通常计为代价 1，但在某些业务场景下也可以赋予不同权重。
从直观上看，如果两个字符串开头字符相同，那么它们对编辑距离的贡献应当从剩余子串继续计算；如果不同，就需要考虑替换、删除或插入哪条路径更优。这种“局部最优可推导全局最优”的性质，正是动态规划能够生效的前提。若采用暴力递归枚举所有操作组合，时间复杂度会达到指数级，无法处理稍长的文本。
二、动态规划的状态与转移
我们定义二维数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符（即 s1[0..i-1]）转换成 s2 的前 j 个字符（即 s2[0..j-1]）所需的最小编辑次数。这里使用前缀长度而非下标本身，是为了让空串情况落在索引 0 上，简化边界处理。
状态转移时，若 s1[i-1] 等于 s2[j-1]，则这两个字符无需额外操作，直接继承 dp[i-1][j-1]；若不相等，则可以从三个方向取最小再加一：从左上角 dp[i-1][j-1] 做替换，从左方 dp[i][j-1] 做插入，从上方 dp[i-1][j] 做删除。边界条件是 dp[0][j] 等于 j（空串插入 j 次），dp[i][0] 等于 i（删除 i 次）。
def edit_distance(s1, s2):
m, n = len(s1), len(s2)
# 创建 (m+1) x (n+1) 的二维列表
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:
dp[i][j] = min(
dp[i - 1][j - 1] + 1, # 替换
dp[i][j - 1] + 1, # 插入
dp[i - 1][j] + 1 # 删除
)
return dp[m][n]
# 示例
print(edit_distance("kitten", "sitting")) # 输出 3
三、复杂度与空间优化
上述实现的时间复杂度为 O(m*n)，空间复杂度同样为 O(m*n)，因为需要完整保存二维表。对于长度在几千以内的字符串，这种开销完全可以接受。而且保留完整 dp 表还能反向追踪具体编辑路径，用于展示“如何从一个串变到另一个串”。
如果只关心距离数值，可以将空间压缩到 O(min(m, n))。核心是观察到每一行只依赖上一行，因此用两个一维数组滚动更新即可。下方代码展示以较短串为列、仅用两行缓冲的写法，在内存受限环境更友好，但会丢失路径还原能力，需按业务权衡。
def edit_distance_space(s1, s2):
# 保证 s2 是较短串，节省空间
if len(s1) < len(s2):
s1, s2 = s2, s1
m, n = len(s1), len(s2)
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] = min(prev[j - 1] + 1, prev[j] + 1, curr[j - 1] + 1)
prev, curr = curr, prev
return prev[n]
print(edit_distance_space("sunday", "saturday")) # 输出 3
四、常见误区与工程注意点
一个常见误区是把编辑距离和最长公共子序列混为一谈。最长公共子序列只关心保留字符，不计入插入删除的对称代价；编辑距离则明确建模了单向或双向的改写成本。另外，在中文场景下，若以字为单位而非字节或词，需先做好分词或字符切分，否则 UTF-8 编码长度会干扰计数。
在工程落地时，如果批量计算大量字符串两两距离，应当考虑利用矩阵运算库或剪枝策略，例如当长度差已超过当前最优值就提前终止。对于模糊搜索，可结合 BK 树或 SimHash 降低全量比对开销，而不是每次都跑完整动态规划。
编辑距离的价值不只在于算出一个数，更在于它用严谨的状态定义把“相似”变成了可计算的问题。
五、小结
通过动态规划计算编辑距离，本质是把字符串转换过程拆成可复用的子问题，用一张表记录前缀之间的最优解。只要抓住状态定义、边界初始化与三类操作转移，就能写出正确且易维护的代码。进一步的空间压缩与路径回溯，则视具体业务对内存和解释性的要求而定。