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)