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.
For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".
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" 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.
Constraints:
1 <= licensePlate.length <= 7licensePlate contains digits, letters (uppercase or lowercase), or space ' '.1 <= words.length <= 10001 <= words[i].length <= 15words[i] consists of lower case English letters.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to finding the shortest completing word involves checking every single word against a given license plate. We'll see if each word contains all the letters in the license plate, ignoring case and non-letters. The shortest word that contains all the letters wins.
Here's how the algorithm would work step-by-step:
def shortest_completing_word(license_plate, words):
normalized_license_plate = ''.join(char.lower() for char in license_plate if char.isalpha())
shortest_word = None
for word in words:
# Check if current word contains all letters
word_contains_all_letters = True
for char in set(normalized_license_plate):
if word.lower().count(char) < normalized_license_plate.lower().count(char):
word_contains_all_letters = False
break
# Update shortest word if applicable
if word_contains_all_letters:
if shortest_word is None or len(word) < len(shortest_word):
# Update shortest_word
shortest_word = word
return shortest_wordThe task is to find the shortest word from a list that contains all the letters of a given license plate. We achieve this by efficiently checking if a word fulfills the license plate's letter requirements and then selecting the shortest valid word.
Here's how the algorithm would work step-by-step:
def shortestCompletingWord(license_plate, words):
license_plate_letter_counts = {}
for char in license_plate:
if char.isalpha():
lower_char = char.lower()
license_plate_letter_counts[lower_char] = license_plate_letter_counts.get(lower_char, 0) + 1
shortest_completing_word = None
for word in words:
word_letter_counts = {}
for char in word:
word_letter_counts[char] = word_letter_counts.get(char, 0) + 1
completes = True
# Ensure the word has all the letters from the license plate
for letter, count in license_plate_letter_counts.items():
if letter not in word_letter_counts or word_letter_counts[letter] < count:
completes = False
break
if completes:
# Update if current word is shorter
if shortest_completing_word is None or len(word) < len(shortest_completing_word):
shortest_completing_word = word
return shortest_completing_word| Case | How to Handle |
|---|---|
| licensePlate is null or empty | Return an empty string or null, as no completing word can be determined. |
| words array is null or empty | Return an empty string or null, as there are no words to search within. |
| One or more words are empty strings | Treat empty strings as invalid words and skip them in the search. |
| licensePlate contains only non-alphabetic characters | Return the shortest word ignoring the license plate completely, essentially finding the shortest word in the words array. |
| All words do not complete the license plate | Return an empty string or null, or throw an exception indicating no solution found. |
| Multiple words complete the license plate with the same minimum length | Return the first such word encountered to satisfy the 'shortest' requirement while handling ties consistently. |
| licensePlate contains uppercase and lowercase letters | Convert the licensePlate to lowercase to perform case-insensitive matching. |
| Extremely long words array and/or words with large lengths may cause time-out issue | Consider using a more efficient data structure to store and compare character frequencies. |