0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Oct 6, 2017 at 10:04
  • $\begingroup$ It would be nice to give some examples $\endgroup$
    – noman pouigt
    Commented Nov 7, 2017 at 3:09

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – thundergolfer
    Commented Oct 7, 2017 at 0:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Commented Nov 5, 2017 at 17:54
  • 1
    $\begingroup$ @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!) $\endgroup$
    – Raphael
    Commented Nov 5, 2017 at 18:04
  • $\begingroup$ @D.W. thanks for your thoughts. Seems like a good option $\endgroup$
    – thundergolfer
    Commented Nov 7, 2017 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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