Shortest Completing Word
Given a string licensePlate and an array of strings words, find the shortest completing word in words.
A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.
Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.
Example 1
Input
licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]Output
"steps"licensePlate contains s, p, another s, and t; only steps contains all of those required letters.Example 2
Input
licensePlate = "1s3 456", words = ["looks","pest","stew","show"]Output
"pest"All words contain
s, but among the shortest valid words, pest appears earliest.Constraints
- 1 <= licensePlate.length <= 7
- licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 15
- words[i] consists of lower case English letters.