String edit distance between strings x, y, with restrictions on 'intermediary' strings This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient. 

Problem

Given a starting string $x$, a target string $y$, and a set of valid strings $V$, find the minimum edit distance between $x$ and $z$ where edits can only be character exchanges and each intermediary string $z_i$ must be in $V$. 

Further constraints on problem


All strings are length 8
The complete character set for strings is $\{A, T, G, C\}$
The starting string $x$ does not need to be in $V$, but $y$ is


My Straightforward an slow-ish solution

When I see an edit-distance problem I immediately think of Dynamic Programming, but tradition Dynamic Programming approaches don't care about the intermediary stages of the string when transitioning between $x$ and $y$, so I wasn't 100% confident in this approach. 

Noticing that given a small enough set $V$ I could quite quickly find all strings in it that were $1$ edit distance from my current string, I went we the following approach. 


Start at string $x$ with target $y$ and set $V$ and current distance $0$


If $x == y$ the return current distance

Mark $x$ as 'seen' by removing it from $V$
Find all strings in $V$ that are 1 edit-distance from current string
recur on all candidate strings, keeping the same target, the updated $V$, and an incremented current distance


This approach isn't too terrible, and with some memoization thrown in it gets even more acceptable, but I get the strong feeling there is a much faster approach to solving the problem with out 'searching' through the set $V$.
I think your approach has merit, but you want to limit the amount of searches on $V$.

Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ with all nodes at Hamming distance one, respectively.

Now the problem is just finding a shortest path from $x$ to $y$.