算法问题，单词接龙问题加强版，请进
有一个字典，包括6万左右个单词，这些单词按照字典序排列。给定两个单词，这两个单词属于这个字典，求出这两个单词的最短编辑距离（与编辑距离有区别）及路径，要求如下：
- 每次变换的单词必须在字典中出现。
- 共有三种变换规则：
1）任意位置添加/删除一个字符，编辑距离为3，例：pro->poro
2）翻转相邻位置的2个字符，编辑距离为4，例：trota->torta
3）将单词某一位置的1个字符修改为另一个字符，编辑距离为5 ,例：torta->torto
求最短编辑距离，及其路径，要求尽可能速度快一些
目前的思路是针对每个单词求出其相关的只需1次操作的单词集合，然后使用深度递进的方法，每次搜索的深度多一层（先搜1层看看是否能达到结果，再搜2层，再搜3层的，以此保证时间复杂度），从出发单词搜索到结束单词
不知道这个问题的有没有更好的算法，文字描述或伪代码即可，谢谢
我这儿有一个开源的项目您看一下，源代码和可运行程序都有：https://github.com/yanlin2579/Sorting-English-article-in-dictionary-order
https://blog.csdn.net/JiuZhang_ninechapter/article/details/113593078
想到一个小优化 就是先算两个单词间的最短距离 然后以这个为层数开始搜索 不需要从第一层开始。还有 感觉从目标字串往开始字串搜索更好。目标很明确 可以考虑一下
这里用迭代加深搜索是不行的，迭代加深找到是变化次数最小的，但是字符串每次变化代价是不同的。不能说最少次数就是最优解
有以下几点想法
- 这题可以用dp来实现，我看题目的标签有动态规划。
- 这是带权重的最短编辑距离，比常见的插入删除替换多了相邻替换，还给定了字典范围。
- 参考博文http://www.hankcs.com/program/java/several-string-edit-distance-achieved.html，博文中的dp公式可以见下方，权重不一样，代码实现需要修改。还有相邻替换没有在下面公式中，但在博文中也给定了代码
我去，我写了半天，好像有坑
我英语不好，单词会的不多，龙刚接上我的大脑cpu就着了，只能帮你到这了。
#!/usr/bin/python3
from random import sample
file = open('/usr/share/dict/words')
word = [x[:-1] for x in file.readlines() if "'" not in x]
file.close()
# [word.remove(x) for x in word if x[-1]=='s' and x[:-1] in word]
begin = False
com = ''
used = []
num = 0
while True:
while True:
usr = input('Your word =')
if usr not in word:
print('Word',usr,'not found!')
continue
elif usr in used:
print('You have used',usr,'before!')
continue
else:
break
if begin and usr[0] != com[-1]:
print('Must begin with',com[-1])
continue
ans = [x for x in word if x[0]==usr[-1]]
com, = sample(ans,1)
num += 1
print('[Your turn %d'%num, com)
used.append(usr)
begin = True
这有类似得单词接龙
https://blog.csdn.net/qq_41231926/article/details/81556690
希望对你有所帮助