英文:
One Edit Distance Away
问题
我目前在休息时间做一些编码工作，以便在大学第二学期开始时保持清新状态。
我遇到了一个CTCI的问题，我对它的理解有些困难，我也看了一些提示，但在如何解决它方面仍然有些困惑。
问题描述
一次编辑：有三种可以对字符串执行的编辑操作：插入一个字符，删除一个字符或替换一个字符。给定两个字符串，编写一个函数来检查它们是否相差一个编辑或零个编辑。
示例输入和输出
- 输入 -> pale，ple 输出 -> true
- 输入 -> pales，pale 输出 -> true
- 输入 -> pale，bale 输出 -> true
- 输入 -> pale，bake 输出 -> false
请不要给我答案
我已经阅读了提示，仍然不明白如何解决这个问题，我理解，为了使插入操作有效，字符串word1和word2的长度必须相差1个字符。
有人能否给我一些建议，告诉我在解决这个问题时应该从哪里开始。谢谢。
英文:
I am currently doing some coding in the break to be fresh ready for semester 2 at university.
I have encountered a CTCI problem which I am struggling to understand, I have also looked at the hints, but still am a bit clueless on how to approach it
The question
One Away: There are three types of edits that can be performed on strings: Insert a character, remove a character or replace a character. Given two strings write a function to check if they are one or zero edits away
Sample INPUT AND OUTPUT
- Input -> pale, ple Output-> true
- Input -> pales, pale Output -> true
- Input -> pale, bale Output -> true
- Input -> pale, bake Output -> false
PLEASE DO NOT GIVE ME THE SOLUTION
I have read the hints, and still do not understand how I should approach this problem, I understand that in order for an insertion to be valid, the length of String word1 and word2 must have a difference of 1.
Can someone please give me some hints on where I should start, when completing this problem. Thank you.
答案1
得分: 2
开始将问题分解为较小的部分。
如果字符串相同，则没有发生更改，因此首先检查它们是否相等。
如果字符串不同，有3种不同的结果：
- 一个字符已被替换
- 一个字符已被删除
- 一个字符已被添加
分别处理每种情况。添加一个新方法来尝试检测每种情况，并从解决方案的主方法中调用这些方法。这将使代码结构更易于理解和测试。
在每种情况下，您将使用循环来比较两个字符串中的字符。
要查找一个字符是否被替换，计算有多少个位置的字符不同。如果恰好有1个位置，它是一个替换。如果超过1个位置，它是一个不同的编辑。
在继续删除和添加的情况之前，确保您可以检测到1个字符的替换。
要查找一个字符是否被删除，计算与上述类似的具有不同字符的位置的数量，但有一个小修改：当您找到差异时，增加其中一个计数器的位置，以便您在一个字符串中跳过一个字符。现在听起来可能很混乱，但一旦您编写了用于检测上述替换情况的工作代码，它将会更清楚。如果遇到困难，您总是可以在这里发布一个新问题，并获得有关您的代码的帮助。
英文:
Start by breaking the problem into smaller pieces.
If the strings are the same, there has been no change, so first check equality.
If the strings are different, there are 3 different outcomes:
- a character has been replaced
- a character has been removed
- a character has been added
Treat each case separately. Add a new method that tries to detect each case, and call these methods from the main method of your solution. This will make the code structure easier to understand and to test.
In each case, you will use a loop to compare the characters in the two strings.
To find if one character has been replaced, count how many positions have different characters. If exactly 1, it's a replacement. If more than 1, it's a different edit.
Make sure that you can detect 1 character replacements before you continue with the remove and add cases.
To find if a character has been removed, count the number of positions with different characters like above, but with a slight modification: when you find a difference, increment the position of one of the counters so that you skip over a character in one of the string. This sounds confusing now, but it will be clearer once you have written working code to detect the replacement case above. If you get stuck, you can always post a new a question here and get help with your code.
答案2
得分: 0
提示，但不是解决方案，不能构成一个很好的栈溢出问题！不过这里有提示：https://en.wikipedia.org/wiki/Levenshtein_distance
英文:
Hint but not solution does not make a good SO question! Here it is though: https://en.wikipedia.org/wiki/Levenshtein_distance
答案3
得分: 0
比较从前面开始的字符串，找出它们共同前缀的长度。
比较从末尾开始的字符串，找出共同后缀的长度。
现在，你可以完全通过两个字符串的长度以及共同前缀和后缀的长度来确定答案。
英文:
Compare the strings starting at the front to find the length of their common prefix.
Compare the strings starting at the end to find the length of the common suffix.
Now you can determine the answer entirely from the two string lengths and the common prefix and suffix lengths.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论