5 ms·
The anagram solution leaves the actual hard part unfinished^. Also, to solve in O(n) you need a bit array (or a database like Postgres that can do an XAND on a
by Supermancho 5y ago
The anagram solution leaves the actual hard part unfinished^. Also, to solve in O(n) you need a bit array (or a database like Postgres that can do an XAND on a string).
> Sort the characters of the words alphabetically. Since anagrams are all made up of the same letters. This will give us the same string for any pair of words that are anagrams of each.
Correct.
> Produce a dictionary of the number of times each letter occurs in each word.
Well, yeah...algorithms aren't the hard part for this kind of question. "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word.
Take a string of zeroes, which is (maxWordlength*26) long.
Each segment of 26 represents a compositional letter from the word. So 100000 00000 00000 00000 00000 is 'a'
Now you can create your dictionary from the sorted word indexes.
pin becomes inp becomes
000000 00100 00000 00000 00000
000000 00000 00100 00000 00000
000000 00000 00001 00000 00000
same as nip (becomes inp, etc)
You can add 26 zero sets, to pad out to the length of longest word, if words are variable length.
^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise.
- malisper 5y ago> "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word. How so? "aab" is an anagram of "baa", but they are not anagrams of "ab".
- Supermancho 5y ago100000 00000 00000 00000 00000 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 aab and baa 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 000000 00000 00000 00000 00000 ab You aren't "counting" the number of characters. You're making an encoding that includes that information, without the aggregation. The aggregation is irrelevant as is the order of duplicate characters.
- tobinfricke 5y agoWhat is XAND?
- deleted 5y ago[deleted]
- mellavora 5y agoexclusive and? Just guessing, I use some of these chips in my synthesizer
- spekcular 5y agoSorry, I don't understand your comment. Why would the proposed "naive" solution of generating a dictionary not work in O(n) time? What is gained by this bit encoding? And as far as I know, XAND does not exist?
- deleted 5y ago[deleted]
- Supermancho 5y agoWhat dictionary? How do you generate it (handwaving notwithstanding, as mentioned)? It all comes back down to encoding, rather than aggregation of letter count.^ > XAND does not exist? XAND being a convenient way to mean binary AND. I thought it was easy to infer. Taking the binary encodings, you can do a binary AND to determine if a set is an anagram subset (or full anagram) with more flexibility. ^Create a hashmap (any searchable K/V will do, redis, postgres, etc). For each word, check to see if encoding exists in set. If not, add key of encoding and value of word. If it exists, you have a match on the search word and the found key's value. Aggregate on a hashmap there for your final output, to avoid adding the same words multiple times.
- spekcular 5y ago> What dictionary? How do you generate it (handwaving notwithstanding, as mentioned)? It all comes back down to encoding, rather than aggregation of letter count.^ OK, first, I'm not sure your original post presents the right reading of the blog post. Sorting and using a dictionary are given in the blog post as two separate solutions, not two components of one solution. (Sorry if I'm mistaken – but it seems to read this way to me?) Regarding your concerns about dictionary generation: I might be missing something, but this doesn't seem so hard? The first thought that comes to mind is to associate to each word a 26-tuple of integers that counts the number of appearances of each letter of the alphabet. This can be done in O(N) time, since it's an O(1) operation for each word (length of words is assumed to be bounded above by some constant). Then 1) Create a (multi)-dictionary with these tuples as keys. Insert is O(1) in the average case, you're doing it N times, so this step is O(N). 2) Go through the dictionary by key and delete all singletons. Again O(N). 3) Print the dictionary by key to get the groups of anagrams. This is O(N) on average. It's not immediately clear to me whether one can do O(N) in the worst case – are you claiming that your way does that? [Of course, this is not so far off from what you're doing. But it illustrates the claim that bit arrays are not necessary.]
- milkey_mouse 5y agoYou could use a lookup table to turn the nth letter of the alphabet into the nth prime number, then multiply those primes together. This "hash" would be unique up to reordering of the primes/letters.
- tester34 5y ago>which is (maxWordlength*26) long. Each segment of 26 represents a >^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise. I hate solutions like this because they'd never be even close to being viable in real world