0
$\begingroup$

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”)

$\endgroup$
6
  • $\begingroup$ Can you provide a formal definition of "a transformation by substitutions"? $\endgroup$ – Steven Jul 20 '20 at 10:54
  • $\begingroup$ @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" $\endgroup$ – Dari Obukhova Jul 20 '20 at 12:20
  • $\begingroup$ 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.. $\endgroup$ – droptop Jul 20 '20 at 19:19
  • 1
    $\begingroup$ @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. $\endgroup$ – Steven Jul 20 '20 at 23:19
  • 1
    $\begingroup$ Please edit the definition from your Jul 20 comment into the question. (You may then remove the comment.) $\endgroup$ – greybeard Jul 25 '20 at 8:14
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$ – Dari Obukhova Jul 20 '20 at 12:21
  • $\begingroup$ 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? $\endgroup$ – Dari Obukhova Jul 20 '20 at 12:28
  • $\begingroup$ Trying all possible substitutions would make your algorithm correct. However care must be used not to end up with an infinite recursion. $\endgroup$ – Steven Jul 20 '20 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.