一编辑距离 [英] One Edit Distance Away

问题描述

我目前正在休息时编写一些代码，为大学第 2 学期做好准备.

I am currently doing some coding in the break to be fresh ready for semester 2 at university.

我遇到了一个我很难理解的 CTCI 问题，我也看过提示，但仍然对如何处理它有点无能为力

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

问题

One Away:可以对字符串执行三种类型的插入字符、删除字符或替换字符.给定两个字符串编写一个函数来检查它们是否是一次或零次编辑

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

样本输入和输出

• 输入 ->苍白，ple 输出->真的
• 输入 ->苍白，苍白输出 ->真的
• 输入 ->苍白，大包输出 ->真的
• 输入 ->苍白，烘烤输出 ->假

请不要给我解决方案我已经阅读了提示，但仍然不明白我应该如何解决这个问题，我知道为了使插入有效，字符串 word1 和 word2 的长度必须相差 1.

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.

推荐答案

首先将问题分解成更小的部分.

Start by breaking the problem into smaller pieces.

如果字符串相同，则没有变化，所以先检查相等性.

If the strings are the same, there has been no change, so first check equality.

如果字符串不同，则有 3 种不同的结果:

If the strings are different, there are 3 different outcomes:

• 一个字符已被替换
• 一个字符已被删除
• 添加了一个字符

分别对待每个案例.添加一个尝试检测每种情况的新方法，并从解决方案的主要方法中调用这些方法.这将使代码结构更易于理解和测试.

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.

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

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.

在继续删除和添加案例之前，请确保您可以检测到 1 个字符替换.

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.

这篇关于一编辑距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！