python – 计算编辑集以将一个字符串转换为另一个字符串的算法？

概述我想计算只使用插入和删除将一个字符串A转换为另一个字符串B所需的编辑,并且需要最少的 *** 作数. 所以像“小猫” – > “sit”会产生一个 *** 作列表,例如(“0处删除”,“0处插入”,“4处删除”,“3位插入’i”,“插入’g’处6” ) 是否有算法执行此 *** 作,请注意我不想编辑距离,我想要实际编辑. 我曾经有过类似的任务.尝试使用A *变体.构造一个给定单词的可能“邻居”的图形,并使用A *向外搜索 我想计算只使用插入和删除将一个字符串A转换为另一个字符串B所需的编辑,并且需要最少的 *** 作数.

所以像“小猫” – > “sit”会产生一个 *** 作列表,例如(“0处删除”,“0处插入”,“4处删除”,“3位插入’i”,“插入’g’处6” )

是否有算法执行此 *** 作,请注意我不想编辑距离,我想要实际编辑.

解决方法 我曾经有过类似的任务.尝试使用A *变体.构造一个给定单词的可能“邻居”的图形,并使用A *向外搜索,距离启发式是在当前单词中更改到达目标所需的字母数.应该清楚为什么这是一个很好的启发式 – 它总是会被低估.您可以将邻居视为只能使用一个 *** 作从当前单词到达的单词.应该清楚的是,该算法将通过略微修改以最佳方式正确地解决您的问题. 总结

以上是内存溢出为你收集整理的python – 计算编辑集以将一个字符串转换为另一个字符串的算法？全部内容，希望文章能够帮你解决python – 计算编辑集以将一个字符串转换为另一个字符串的算法？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。