#748
Shortest Completing Word
pupil · 420 · lc easy +25 · verified · 62.8% accepted · 630 likes · top 64%
Description
Given a licensePlate string and a list words, a word is "completing" if it contains at least as many occurrences of each letter in licensePlate (case-insensitive; digits and spaces are ignored). Return the shortest completing word in words. If multiple words tie for shortest, return the one that appears earliest. An answer is guaranteed.
Example 1:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.
Example 2:
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.
Code
1
2
3