Reference no: EM131666928

Question: Modify Exercise to allow words of arbitrary length and to allow transformations in which we add or delete one character. The cost of adding or deleting a character equals the length of the longer string in the transformation while a single-character substitution only costs 1. Thus ark, ask, as, was is a valid transformation from ark to was and the cost is 7 (1+3+3).

Exercise: A word can be changed to another word by a one-character substitution. Assume that a dictionary of five-letter words exists. Give an algorithm to determine whether a word A can be transformed to a word B by a series of one-character substitutions, and if so, outputs the corresponding sequence of words. For example, bleed converts to blood by the sequence bleed, blend, blond, blood.