# 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.

1. Start at string $x$ with target $y$ and set $V$ and current distance $0$
• If $x == y$ the return current distance
2. Mark $x$ as 'seen' by removing it from $V$
3. Find all strings in $V$ that are 1 edit-distance from current string
4. 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$.

• So it's not edit distance at all, but Hamming distance. That makes the problem without V trivial, and may provide a better starting point than the edit distance recurrence. – Raphael Oct 6 '17 at 10:04
• It would be nice to give some examples – noman pouigt Nov 7 '17 at 3:09

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$.
• @thundergolfer, You can explore the graph lazily, only generating nodes (and the edges out of them) as needed. Start by generating the node for $x$, then lazily add nodes to the graph as needed. – D.W. Nov 5 '17 at 17:54