Is my recursive algorithm for Equivalent Words correct?

Question

Here is my problem.

Problem Given two words and a dictionary, find out whether the words are equivalent.

Input: The dictionary, D (a set of words), and two words v and w from the dictionary.

Output: A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output "v and w are not equivalent."

I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?

 EquivalentWordsProblem(v, w, D)
 1.m <- len (v)
 2.n <- len (w)
 3.substitutions = [] #array to save substitutions 
 4.if m != n:
 5. return "v and w are not equivalent"
 6.else
 7.for i <- m to 1 <-1 do
 8. for j <- n to j <- 1 do
 9. if v[i] != w[j]:
 10. substituted_word <- v[1...i-1]+v[j] #we substitute v[i] for w[j]
 11. if substituted_word in D:
 12. substitutions.append(substituted_word)
 13. return EquivalentWordsProblem(v[1...m-i], w, D) #recur on the string of length m - i
 14. else:
 return EquivalentWordsProblem(v[1...m-1], w, D) #recur on the string decreasing its length by 1
 15.if len(substitutions) != 0:
 16. return substitutions 
 17.else
 18. return ("v and w are not equivalent")

• Steven: Can you provide a formal definition of "a transformation by substitutions"?
• Dari Obukhova: @Steven, thanks for your reply. Here is the definition of problem "Transform one English word into another by going through a series of intermediate English words, where each word in the sequence differs from the next by only one substitution. To transform head into tail one can use four intermediates: head → heal → teal → tell → tall → tail. We say that two words v and w are equivalent if v can be transformed into w by substituting individual letters in such a way that all intermediate words are English words present in an English dictionary"
• droptop: You can adapt the Min Edit Distance between two strings algorithm to not calculate the min but rather keep track of each transformation (delete, replace or insert) and then return the list of transformations if the recursion terminates on exhaustion of both strings. You'll have to test if each transformation is in D before recursing..
• Steven: @droptop. That won't work. The only changes considered by the classical min edit-distance algorithm involve characters that are in at least one of the input strings. There are feasible instances of the problem in the question that require substitutions involving character that are neither in $u$ nor in $v$. See my answer for a counterexample.
• greybeard: Please edit the definition from your Jul 20 comment into the question. (You may then remove the comment.)

Answer 1

Your algorithm is not correct. Here is a counterexample: $D$ contains the words $aa,bb,ac,bc$; $v=aa$; and $w=bb$.

A transformation is possible $(aa \to ac \to bc \to bb)$ but your algorithm won't find it.

• Dari Obukhova: thanks so much for your kind reply. I am new to algorithms so I would be very grateful if you give me some hint about making my algorithm correct. Thanks!
• Dari Obukhova: Do I need to consider all symbols present in the words of dictionary as possible j's for substitution or am I getting your explanation via counterexample wrong?
• Steven: Trying all possible substitutions would make your algorithm correct. However care must be used not to end up with an infinite recursion.