求解释判断两字符串Levenshtein距离是否为2的Python代码原理

代码核心逻辑说明 #

这段代码是专门用于判断两个字符串Levenshtein距离是否恰好为2的压缩带状动态规划实现，利用「仅需判断距离≤2时，只需要计算DP表中主对角线左右偏移不超过2的单元格」的特性，把DP状态压缩到了固定长度为5的数组中，所有距离大于2的状态都用4统一表示，避免无效计算。

疑问点逐一解答 #

1. 初始值t = [4, 4, 1, 2, 3]的作用 #

t是存储上一轮DP状态的压缩数组，长度固定为5，分别对应当前处理位置主对角线偏移-2、-1、0、1、2的五个状态值。
初始状态对应还未处理str1任何字符的DP第0行，标准DP中第0行的规则是dp[0][j] = j（插入j次得到对应前缀），这里：

• 前两个4对应偏移-2、-1的无效状态，因为距离已经超过2，统一用4表示
• 后三个1、2、3对应偏移0、1、2的初始状态，因为代码里所有DP值都做了+1处理，对应实际距离0、1、2

2. li()函数的设计作用 #

li是统一的边界处理工具函数：

• 负索引直接返回对应值：是因为计算str2的位置i+j-2时，j较小的情况下索引会为负，正好对应str2的前缀匹配逻辑，Python原生支持负索引，不需要额外处理，符合DP转移的边界需求
• 仅捕获正索引越界返回None：当索引超过字符串/列表长度时，代表没有对应字符，统一返回None代表该位置字符不匹配，简化后续转移逻辑的判断

3. li(t, j + 1) or 4的逻辑作用 #

这行是处理上一轮状态数组的边界：
t的长度固定为5，当j是最后一个索引（4）时，j+1=5会超出数组范围，li返回None，这时候对应位置的状态距离已经超过2，用4代替即可，不影响min函数的计算结果，统一了边界和正常值的处理逻辑。

4. 变量p的含义 #

p就是当前正在计算的DP单元格值，完全对应标准Levenshtein DP的转移公式：

dp[i][j] = min(
    dp[i-1][j-1] + (str1[i] != str2[j]), # 替换/匹配代价
    dp[i][j-1] + 1, # 插入代价
    dp[i-1][j] + 1 # 删除代价
)

代码里的p计算就是把三个转移方向压缩到了一行：

• t_val - (str1_symb == li(str2, i + j - 2))对应左上角的替换/匹配代价
• 第二个参数p对应左边单元格的插入代价
• li(t, j + 1) or 4对应上边单元格的删除代价
  最后加1是代码统一做的偏移处理，实际距离等于最终p值减1。

返回值逻辑说明 #

最后li(t, len(str2) - len(str1) + 2) == 3的判断，是取最终状态中两个字符串长度差对应的偏移位置的值，等于3的话对应实际Levenshtein距离为3-1=2，正好符合我们要的判断条件。

内容的提问来源于stack exchange，提问作者Simd