Levenshtein编辑距离和不同编辑集

Question

我刚问了几个问题，但我被困在了一个Levenshtein编辑距离问题上。

所以问题的第一部分是：

STRONGEST和TRAINERS字符串之间的Levenshtein编辑距离是多少？

我把它算成6。但下一个问题是

将d设为在部分(so 6)中找到的编辑距离。有多少不同的集合 of d‘edits’(插入、删除或替换)会将字符串STRONGEST更改为字符串TRAINERS？

有谁能解释一下我是如何发现这里有多少不同的集合，以及你是如何找到解决方案的？

Answer 1

如果您对第一个问题使用了回忆化表方法，只需转到表的右下角(在那里您获得最小的编辑距离)并跟踪所有可能的最小编辑路径。所有这些路径将为您提供不同的编辑集。有关如何追溯的参考，您可以看到打印两个字符串的LCS问题的这解决方案。

您还可以参考上面提到的页面上的我的意见。