OneAway

This is from the Udemy course “Data Structures and Algorithms bootcamp”.

This is a bit of a fiddly one. You are tasked with writing code that will return true if two strings are “one edit” away, i.e., one longer, one shorter, or one substitution. Here is the challenge and unit tests:

I ended up with the same solution as the course director it seems:

  1. If there is greater than 1 difference in size between the two strings, immediately that is of course a fail.
  2. First test for a substitution, in which case the strings are of equal length and in only one position there are two observed characters. E.g., for “pale” and “bale” element 0 has a ‘p’ or ‘b’, and only one char at each other element
  3. Second test for an insertion. Insert a non alphanumeric char e.g., ‘_’ at the position where two chars at the same index in both strings don’t match. If you are now adding a second ‘_’, then return false. The course uses Java, so you will have to insert a character into the string array manually.
Remember to increment insertions first, you have added a one character buffer onto the end of the smallest string, hence you will go out of range if you try to insert twice, and you won’t need to.

Alternatively you may be able to use a “Trie” datastructure.. which are designed for these sorts of problems… More on that later!

Leave a Reply

Your email address will not be published.