# Algorithm to reconstruct sentence from shuffled string

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 ?

• 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. – D.W. Dec 18 '16 at 6:52

• 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?) – D.W. Dec 19 '16 at 4:47
• @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... – j_random_hacker Dec 19 '16 at 10:12