Find matching dictionary words given a Scrabble tray

Question

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.)

Answer 1

The way to use a trie here is to sort the letters of each dictionary word:

[ AD, ADD, DAD ] becomes A > D [ ad ] > D [ add, dad ]

Then walk the trie and stop descending when isWordInTray returns false.

Worst-case complexity is unchanged (arguably worse, since sorting time is not linear); actual runtime is greatly improved.

Answer 2

I have previously looked at this problem - many years ago. The first step is to create an indexed list of all the words in the dictionary, with the characters sorted in alphabetical order. This is a one-off cost O(n) [Where n in this case is the size of the dictionary, not the number of letters in the Scrabble tray].

Now, for each search of n letters, you can filter the list where the list element contains any letter that does not exist in the Scrabble tray. For example, if you had DDA in your hand, the word DEAD would be excluded because E does not exist in your hand. This should be O(n) [Where n in this case is the size of the dictionary, not the number of letters in the Scrabble tray].

The indexing/ordering of letters in the dictionary can be used to your advantage (especially if you use a jagged list), because some words are anagrams of others. So a check of the list for DALE, DEAL, LADE and LEAD should only cost one cycle in the search - four words for one! In addition, if your lowest character in your hand is not A (e.g. say it is M), you can use the indexing on the first character to remove a large swath of words in a single hit - similarly for the highest character in hand (e.g. if the highest character is D, you can stop searching the index when the first character is E).

So now, if you are doing a single search, your cost is at most O(2n), but probably more in the order of O(n + k*n/2). where k is the number of searches you will do. Happy to be corrected on my assessment of O because it has been a few decades since I last looked at formal definitions of O.