c++ - Levenstein 程序差异？

Question

我有一个 C++ 任务，我不确定如何解决这个问题。所以你有一个 startString 和一个 ENDSTRING。重点是使用给定的一组操作将 startString 转换为 ENDSTRING:

1. 插入字符
2. 删除字符
3. 替换字典中的子串
4. 移动子串(向左)
5. 反转子串

并且您使用的操作应尽可能少

于是google了一下，发现这是字符串重构问题。这是编辑距离，尤其是 Levenshtein 距离算法。

但 Levenshtein 算法不会给你你所做的步骤 - 它只给你步骤数。我必须编写一个算法，以尽可能少的操作将 givenString 重建为 ENDSTRING，并编写一个文件来描述到目前为止所采取的步骤。

你能指导我应该使用哪种算法吗，因为 Levenshtein 只给你步数，但我还需要它们的数量和一个包含实际步骤的列表。

谢谢

Answer 1

基本上，您必须稍微修改 Levishtein 算法。由于它是动态规划的一个例子，动态规划状态空间的一个特定状态的计算对应于备选方案的特定选择。据我了解，您有两种选择:

1.) 使用一些辅助数据结构，在其中为每个状态存储选择值对应；

2.) 不使用辅助数据结构，但是一旦评估了状态空间，您就使用回溯来查看哪些选择是可能的。

选项 2.) 可能会导致更少的代码，但选项 1.) 可能更容易理解。