您的“实施”有几个缺陷：
(1)它应该以def lev(a,b)：开头,而不是def lev(s1,s2):.请先了解(a)运行代码之前的好习惯(b)引用您实际运行的代码(通过复制/粘贴,而不是(容易出错)重新键入).
(2)没有终止条件;对于任何参数,它最终将最终尝试评估lev(“”,“”),如果不是Python实现限制,它将永远循环：RuntimeError：超出最大递归深度.
您需要插入两行：
if not a: return len(b)
if not b: return len(a)
使它工作.
(3)Levenshtein距离是递归定义的.没有“这个”(唯一的)算法.递归代码在教室外很少见,然后只能以“稻草人”的身份出现.
(4)朴素实现需要时间和内存与len(a)* len(b)成比例……那些字符串通常不会比4到8长一点吗？
(5)你非常天真的实现更糟糕,因为它复制了输入的切片.
你可以在网上找到工作不太天真的实现… google(“levenshtein python”)…寻找使用O(max(len(a),len(b)))额外内存的实现.
你问的是什么(“与其他字符串编辑距离最短的字符串的编辑距离.”)没有意义……“字符串”??? “一个巴掌拍不响” ：-)
您可能想要的(找到具有最小距离的集合中的所有字符串对),或者可能只是最小距离,是一个简单的编程练习.你尝试过什么？
顺便说一句,通过一个简单的算法找到那些对将需要执行lev()的O(N ** 2)执行,其中N是集合中的字符串数…如果这是一个真实世界的应用程序,你应该看看使用经过验证的代码而不是自己编写代码.如果这是家庭作业,你应该这样说.