CODEWITHSUNDEEP
javastringalgorithm
E-SetPrimeEpsilon
E-SetPrimeEpsilon

Reputation: 123

One Edit Distance Away

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

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.

Upvotes: 3

Views: 653

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59174

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.

Upvotes: 0

Joni
Joni

Reputation: 111239

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.

Upvotes: 2

drekbour
drekbour

Reputation: 3081

Hint but not solution does not make a good SO question! Here it is though: https://en.wikipedia.org/wiki/Levenshtein_distance

Upvotes: 0

Related Questions