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

• I thought of this approach later on, but it intuitively sounded less efficient for a single-use case, because of the cost of constructing the graph. Perhaps I should explore this option properly. Oct 7 '17 at 0:59
• @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
• @D.W. Good thought. In a unit-cost graph, an area around the starting node with the "radius" of the target distance will be explored. That's still potentially an exponentially large space -- but now in the distance, not string length. (SSSPP algorithms that compute simulatenously starting from both end nodes can profit here!)
– Raphael
Nov 5 '17 at 18:04
• @D.W. thanks for your thoughts. Seems like a good option Nov 7 '17 at 3:15