Word from a License Plate

Easy

You are given a license plate plate, a string of digits, English letters in either case and spaces, and an array of words words. A word *covers* the plate if it contains every letter of the plate, counting repeats: digits and spaces are ignored, letter case does not matter, and a letter that appears several times on the plate must appear at least that many times in the word. For example, the plate "kK 77a" is covered by "kayak" and "knack" but not by "kale". Return the shortest word in words that covers the plate. If several words tie, return the one that comes first in the array. At least one covering word is guaranteed to exist.

Example 1

plate='7KA 2k9', words=['kayak', 'kick', 'karaoke', 'snack'] → 'kayak'

The plate holds k, a and another k. "kick" lacks an a and "snack" has only one k, while "kayak" and "karaoke" both fit; "kayak" is shorter.

Example 2

plate='B 404', words=['crab', 'blue', 'bird', 'rob'] → 'rob'

Only the letter b is needed. Every word has one, and the shortest is "rob".

Example 3

plate='Ox 12', words=['axon', 'oxen', 'box', 'fox'] → 'box'

All four words fit; "box" and "fox" tie at length 3, and "box" wins because it comes first.

Constraints

1 ≤ plate.length ≤ 20
plate consists of digits, English letters and spaces
1 ≤ words.length ≤ 1000
1 ≤ words[i].length ≤ 15
words[i] consists of lowercase English letters
at least one word covers the plate

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String