EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th bit indicates whether the word contains the i-the letter in the alphabet.
As I was tackling an interview problem I came up with this tree-like data structure. Actually it IS a binary tree that is maximum 26(English alphabet size) nodes deep. Basically the problem is:
There are a set of dictionary words and a set of license plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the letters in the license plate, irrespective of the order of characters
This data structure is specifically designed for the problem of finding words from a given list containing all letters from a set of letters.
I call this operation getSupersetWords().
It can also be used for finding words containing ONLY a set of letters.(In fact my empirical tests show that this is the use case giving the best performance gain over linear search (over 16 times faster on average for a list of 73k English words)).
I call this operation getSubsetWords().
To give you an example:
Lets say we have list of words = [ “cat” ,”dog” “cow”, “case”].
On query getSupersetWords([‘a’, ‘c’]) we get [“cat”, “case”].
On query getSubsetWords(['c', 'o', 'w', 'a', 't']) we get ["cat", "cow"].
How to add a string to this data structure ?
As I said earlier the data structure is a binary tree.
At every level of the tree we make a decision. If the word contains the next letter of the alphabet(we start from 'a' at level 1) we go right, else we go left.
If we have made all the 'right' possible decisions for the given word we place it in the current node.(A node contains a reference list of strings).
How to answer a query from this data structure ?
Now to answer a getSubsetWords() query we traverse the tree recursively in DFS making both decisions if the query contains the character at the current letter, or 'left' if it doesn't and adding the words at the given Node to a list
(this is VERY confusing to type out...but not so much in code :/).
It sounds confusing, that's why I made a simple diagram illustrating the idea.
Assume we have a list of strings = {"a","aaa","baa","ab","bb"}.
Now If we had 'z' in the list the tree would be 26 nodes deep, but because the 'biggest' letter is 'b' We only need 3 levels.
The circle shapes are lists of strings, the rectangles are the nodes. I was wondering if this structure is something I have 'invented' or it is already well known, (Which probably is the case :).