距离编辑为1

Question

我目前正在休息期间编写一些代码，以便在大学第二学期开始时保持清新。

我遇到了一个CTCI问题，我很难理解，我也看了提示，但仍然不太清楚如何处理它。

问题

一次编辑：字符串可以执行三种类型的编辑操作：插入一个字符，删除一个字符或替换一个字符。给定两个字符串，请编写一个函数来检查它们是否只相差一个或零个编辑

样例输入和输出

• 输入 -> pale, ple 输出-> true
• 输入 -> pales, pale 输出 -> true
• 输入 -> pale, bale 输出 -> true
• 输入 -> pale, bake 输出 -> false

请不要给我答案 我已经阅读了提示，但仍不理解该如何处理这个问题。我知道为了进行插入操作，字符串 word1 和 word2 的长度必须相差1。

请问有人能给我一些提示，告诉我该从哪里开始解决这个问题。谢谢。

- E-SetPrimeEpsilon

---

你怎么知道一个字符是否被删除了？ - jhamon

长度可以多或少1个字符，但您还必须检查较小字符串中的所有字母是否存在于另一个字符串中，这样它们将相差1个或0个编辑步骤。 - maha

Answer 1

首先将问题分解为更小的部分。

如果字符串相同，则没有变化，因此首先检查它们是否相等。

如果字符串不同，则有三种不同的结果：

• 字符已被替换
• 字符已被删除
• 字符已被添加

将每种情况单独处理。添加一个新方法来尝试检测每种情况，并从解决方案的主方法中调用这些方法。这将使代码结构更易于理解和测试。

在每种情况下，您将使用循环来比较两个字符串中的字符。

要查找是否替换了一个字符，请计算具有不同字符的位置数量。如果正好为1，则是替换。如果超过1，则为不同的编辑。

确保在继续删除和添加操作之前，可以检测到1个字符的替换。

要查找是否删除了一个字符，请像上面那样计算具有不同字符的位置数，但稍作修改：当您发现差异时，请增加其中一个计数器的位置，以便跳过其中一个字符串中的一个字符。现在听起来可能有点混乱，但是一旦您编写了可用于检测替换情况的工作代码，它将变得更加清晰。如果您遇到困难，您总可以在这里发布一个新问题，并获得有关您的代码的帮助。

- Joni

Answer 2

提示而非解决方案并不是一个好的SO问题！不过这里有一个链接：https://en.wikipedia.org/wiki/Levenshtein_distance

- drekbour

Answer 3

比较字符串的前缀，以找到它们共同的长度。

比较字符串的结尾，以找到公共后缀的长度。

现在，你可以完全从两个字符串的长度和公共前缀和后缀的长度来确定答案。

- Matt Timmermans