One Edit Distance Away

user_13710987 0
Viewed 437

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.

algorithm java string
3 Answers

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.

user_3187580
user_6283180

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.

user_54835260
Related