2
$\begingroup$

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word).

But what about finding multi-word anagrams? For example "Eleven plus two" is an anagram of "Twelve plus one". In other words, given a multi-word phrase $w_1,\dots,w_s$, find a set of $s$ words that form a multi-word anagram.

I've thought about this for a bit and I came up with a $O(n^2)$ algorithm for all 3-word anagrams of a string, where $n$ is the number of words in the dictionary -- it basically comes down to the 3-sum problem but for histograms instead of integers. Are there any better algorithms? Assume the set of words is valid English words and $|s| \le 30$.

$\endgroup$
  • $\begingroup$ What is you $O(n^2)$ solution? $\endgroup$ – paparazzo Jul 19 '17 at 12:59
  • $\begingroup$ Sort by length in $O(n^2 logn)$ then sum in order $O(n^2 logn)$ then anagram in $O(m)$ $\endgroup$ – paparazzo Jul 19 '17 at 13:05

Your Answer

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

Browse other questions tagged or ask your own question.