This is a question I was asked in an interview, below is a cleaned-up copy of the answer I gave. Apparently this answer was not satisfactory. How can it be improved?
Question: Given a dictionary of words (a text file with 100000+ entries) and a list of n
letters with possible repeats (i.e. a Scrabble tray), return the list of words which can be formed from some or all of the letters in the tray.
function scrabble(dictionary, tray) {
return dictionary.filter(w => isWordInTray(tray, w));
}
function isWordInTray(tray, word) {
// build multiset of letters in tray
let counts = {};
for (const letter of tray) {
if (counts[letter] === undefined) {
counts[letter] = 1;
} else {
counts[letter]++;
}
}
// take letters from the word and decrement tray count
for (const letter of word) {
if (counts[letter] > 0) {
counts[letter]--;
} else {
return false;
}
}
return true;
}
//---------------
// dictionary (full dictionary contains 178691 entries)
const dict = ['AA', 'ABSORBABILITIES', 'AD', 'ADD', 'BAD', 'DAD', 'FOO']; // ...
// test case
const exampleTray = ['D', 'D', 'A'];
console.log(scrabble(dict, exampleTray));
// expected correct answer (in any order)
// [ 'AD', 'ADD', 'DAD' ]
Caveats
- The interviewer said that the problem was "kind of like Scrabble", this was the only mention of Scrabble. The size of the tray was given simply as
n
(it was described as a list of letters, not a tray). - The full dictionary was given to me as a text file, it is sorted and has 178691 entries. I've included a minimal subset which works with the test case I was given in the interview.
counts
is a hashtable but I could have used a 26-element array instead to get O(1) inserts and lookups which improves the worst case from O(n), but n = 26, so it's not a big deal.- I'm not looking for micro-optimizations for special cases: I'm only seeking to decrease the big-O worst case complexity.
Alternative Approaches
These are the other approaches which spring to mind:
Approach 2: Generate all words
The opposite approach is to generate all words from the tiles and look them up in the dictionary, but if we treat the tray as a multiset of letters then the number of words we will generate is a multiset permutation and that's just for the case where len(word) = len(tiles) without considering all the shorter words which can be formed.
The size of the tray was given as n
, while in the game of Scrabble it's at most 7 (news to me as I don't play Scrabble), the interviewer never gave this restriction, so presumably max(n) = max(len(word) in dict) which is "ABSORBABILITIES" at 15 letters. That's going to be a huge search space. I asked what n
was and he said "anything".
If my understanding is correct, the worst case for multiset permutations is when each letter in the tray is unique, because this is simply the number of permutations which is n!
. Again, this doesn't account for the need to also find words shorter than the tray length.
7! = 5040
, so for an actual Scrabble tray, generating all words is feasible, but at 9!
we've generated more words than are in our dictionary and by 15!
there's over a trillion.
Approach 3: Use a trie?
When I see words being looked up in a dictionary, I think of a trie (prefix tree). What I can't see is what it would offer in this case, especially w.r.t big-O worst case complexity.
Is there something I'm totally missing?
Big-O
Assuming that all words are of length w
and the tray is also that length, the dictionary is of length n
, and there are no anagrams; the complexity should be O(n*w)
.
(This also assumes that counts
is replaced with an array as mentioned above.)