2
$\begingroup$

Given a dictionary of words, and given a string which is an anagram of concatenation of group of words from the dictionary, is there an efficient algorithm to find valid set of words that can form this string ?

eg1: dict = [ 'dog', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ]

If we join the words in the answer to form the string, we can see that it is an anagram of the input string s

eg2: dict = [ 'dog', 'act', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ] or [ 'act', 'cat', 'dog' ] or [ 'act', 'act', 'dog' ]

In the above case any of the above list is valid as the string formed by them is an anagram of the input string s

We can brute force but there seems to be overlapping sub problems. Can this be solved in polynomial time ?

$\endgroup$
  • 2
    $\begingroup$ Sounds hard. One trivial note: you can sort every word internally and remove duplicates (e.g., cat -> act, dog -> dgo, etc.). But the problem still seems hard in general. It can also be reduced to a linear algebra problem: given a $n \times 26$ matrix $M$ of non-negative integers and an integer 26-vector $y$ of non-negative integers, find a $n$-vector $x$ of non-negative integers such that $Mx=y$. However, I don't know how to solve that kind of linear algebra problem efficiently, either, due to the non-negativity restriction. $\endgroup$ – D.W. Dec 18 '16 at 6:52
2
$\begingroup$

This is NP-hard, so it's very unlikely there's a polynomial-time solution. To see this, notice that any instance of the NP-hard problem Exact Cover can easily be encoded as an instance of your problem in such a way that there is a solution to this encoded instance if and only if there is a solution to the original Exact Cover instance.

$\endgroup$
  • 2
    $\begingroup$ Nice observation! (Hmm. I guess NP-hardness applies to an unbounded alphabet, so this doesn't rule out the possibility of an algorithm whose running time is exponential in the size of the alphabet. In this case the alphabet size is 26, so an algorithm with running time $2^{26}$ might be feasible. But maybe that's too much to hope for. The problem feels like it might be even harder than Exact Cover (on an alphabet of size 26), or at least, I can't think of how to use an algorithm for Exact Cover to solve this problem. Can you?) $\endgroup$ – D.W. Dec 19 '16 at 4:47
  • 1
    $\begingroup$ @D.W.: Thanks, and yes, my reduction doesn't show that it's NP-hard for a bounded alphabet, though it might be possible to show that with a more clever reduction. So yes, there might be an $O(2^{26}n^{O(1)})$ algorithm. Are dictionary words with multiple copies of the same letter the obstacle you see to applying an Exact Cover algo more or less directly to this problem? I don't yet see a poly-time way around that... $\endgroup$ – j_random_hacker Dec 19 '16 at 10:12
  • $\begingroup$ Yes, that plus the fact that we can re-use the same word multiple times. $\endgroup$ – D.W. Dec 19 '16 at 15:03
  • $\begingroup$ I think the latter problem can be handled by just letting there be multiple copies of sets in the EC instance. (This could require the instance to be inflated by "only" a polynomial amount, but in practice, massively...) $\endgroup$ – j_random_hacker Dec 19 '16 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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