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