Find shortest word in a dictionary that contains letters from a licence plate.
We look at licence plates and try to find a word from the dictionary that includes all the letters from the licence plate. The shorter the word, the better. The licence plates start with two or three letters, then they are followed by 5 characters, from which at most 2 are letters, the rest are digits.
Your goal is to write code that will find the shortest words for 100 licence plates. You are given a dictionary.
E.g. for the licence plate "RT 123SO" the shortest word would be "SORT", for "RC 10014": "CAR".
[The good questions to ask to clarify]
- how to treat duplicate letters? (keep)
- are spaces and digits necessary? (drop them)
- should the letter order be preserved? (no)
- what case are the plates and the words from dictionary? (plates upper, dict mixed)
- is the dictionary sorted? (lexicographical order) - how large is the dictionary? (~ million entries)
Do we have some time for pre-processing?
If yes, I would create a hashmap which links every letter of the alphabet to the list of words from the dictionary that contain this letter. This will take O(dicLength) time (assuming each word has a length bound by 20 or something).
Then for a given plate, find the intersection of all the lists of this plate's characters, and pick the smaller word (if these lists are ordered by length we can optimize this step by stopping early).