Finding the subset of a dictionary that has the minimum edit distance to a given string

I'm looking for the most efficient way of solving an Levenshtein edit distance problem.

We are given as input:

1. A set of strings S of size n <= 8, with average length m <= 50
2. A target string t of length l <= 50

Our task is to 'align' t with S i.e:

Find the subset s* of S, where concat(s*) has the minimum Levenshtein edit distance (among all the subsets) with t

Some thoughts:

1. For 2 strings of length l1 and l2, we could use the standard dynamic programming algorithm which has O(l1*l2) time complexity
2. Brute forcing this would require us to compute editDistance(t, concat(s')) for each subset s'. This would be approximately O(l.m.n!)
3. This could be optimized a bit by memoizing the results i.e if we are computing editDistance(t, S[1, 2, 3, 4]) we could re-use the computation from S[1, 2, 3])
4. The other option I could think of is to construct a Trie or DAWG (Directed Acyclic Word Graph)

But, I'm not an expert on this, so I might be missing a better solution. How would we do this efficiently?

• It is a good question. Could you please give reference to where you find this problem? Commented Aug 3, 2023 at 21:57
• What are the constraints on the running time of the algorithm? Commented Aug 4, 2023 at 10:25
• Concatenation is not defined for a set. Do you mean "among all permutations" or is S a sequence ?
– user16034
Commented Sep 3, 2023 at 18:26
• If the strings in s, and t have roughly the same length, most minimal matchings should be with a single string, because m deletions (to reach the same length) compete with m substitutions.
– user16034
Commented Sep 3, 2023 at 18:32

Try all possible permutation and combination of the set $$S$$. There are exactly $$\sum_{r = 1} ^{8} \mathsf{8Pr}$$ such possibilities for $$n = 8$$. This sums to exactly 109600.
For each subset $$s^*$$ of $$S$$, find the edit distance to target string $$t$$ using the standard DP algorithm. This will take time $$l_S \times l$$ where $$l_S$$ is the total length of all the strings in $$S$$ and $$l$$ is the length of string $$t$$. Since $$l_S$$ could be $$400$$ and $$l$$ could be $$50$$, the total running time is ~ $$2 \times 10^9$$.
You can further optimize the algorithm. In the standard DP algorithm, the algorithm stores the minimum edit distance of all the pairs of suffixes of two given strings $$a$$ and $$b$$. In the current problem, the string $$t$$ is fixed; however $$concat(s^*)$$ varies depending on subset $$s^*$$. However, note that some suffixes of $$concat(s^*)$$ overlaps for different $$s^*$$. You can show that there at most $$S_l \cdot (nC0 + nC1 + nC2 + \dotsc + nCn)$$ possible different suffixes of the concatenated string $$concat(s^*)$$ over all possible subsets $$s^{*}$$ for $$n = 8$$. This sums to at most $$S_l \cdot 2^{8} \leq 102400$$. Thus, the algorithm only needs to find edit distance of $$102400 \times 50$$ possible pairs of suffixes. Thus, the algorithm can be implemented in ~ $$5 \times 10^{6}$$ computation steps, which is doable in $$1$$ sec on regular personal computers.
• By augmenting the standard DP with an extra "column" of edges for each $s_i$ that deletes that entire string for zero cost, it's possible to consider only concatenations of permutations that use all 8 strings in $S$. This drops the number of possibilities from 109600 to $8! = 40320$. Commented May 2 at 0:16