Determine if a string can be transformed to another string when only insert/remove/replace operations are allowed

Question

I must write a function that takes two words (strings) as arguments, and determines if the first word can be transformed into the second word using only one first-order transformation.

• First-order transformations alter only one letter in a word

• The allowed transformations are: insert, remove and replace

  • insert = insert a letter at any position in the word
  • remove = delete a letter from any position in the word
  • replace = replace a letter with another one

Any suggestions? Any Java examples would be great!

Answer 1

Think: If you're only allowed a single transformation, then the difference in length between the "before" and "after" words should give you a very strong hint as to which of those three transformations has any chance of being successful. By the same token, you can tell at a glance which transformations will be simply impossible.

Once you've decided on which transformation, the rest of the problem becomes a job for Brute Force Man and his sidekick, Looping Lady.