748. Shortest Completing Word
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 57.6%
Problem Breakdown
The problem requires finding the shortest word in a given list that contains all the letters from a provided license plate string. The license plate may contain numbers and spaces, which should be ignored. Letters are case-insensitive, meaning ‘A’ and ‘a’ are considered the same. If multiple words have the same length, the first one encountered in the list should be returned.
Inputs:
licensePlate: A string containing letters (uppercase or lowercase), numbers, and spaces.words: An array of strings where each string consists only of lowercase English letters.
Outputs:
- The shortest word from the
wordsarray that contains all the letters inlicensePlate.
Implicit Constraints/Edge Cases:
- The license plate length is between 1 and 7 characters.
- Each word in the list has a length between 1 and 15 characters.
- There is guaranteed to be at least one valid completing word in the list.
Intuition
A brute-force approach would involve checking each word against the license plate by counting occurrences of each letter. This method would have high time complexity due to repeated counting for each word. A more efficient approach involves pre-processing the license plate to count its letters and then iterating through the words, updating the counts as necessary.
The key insight is to use a hash table (dictionary in Python) to store the frequency of each letter in the license plate and then check each word against this dictionary. This reduces the need for repeated counting and allows us to efficiently determine if a word is a completing word.
Approach
-
Pre-process the License Plate:
- Create a dictionary to count the occurrences of each letter in the
licensePlate, ignoring numbers and spaces, and treating letters as case insensitive.
- Create a dictionary to count the occurrences of each letter in the
-
Iterate Through Words:
- For each word in the
wordslist, create a frequency dictionary for its letters. - Check if this word’s frequency dictionary contains at least the same number of occurrences for each letter as the pre-processed license plate dictionary.
- For each word in the
-
Track the Shortest Completing Word:
- Keep track of the shortest word that meets the criteria. If multiple words have the same length, retain the first one encountered.
-
Return the Result:
- After checking all words, return the shortest completing word found.
Complexity Analysis
- Time Complexity: O(n * m), where n is the number of words and m is the average length of a word. Pre-processing the license plate takes constant time.
- Space Complexity: O(1) for the dictionary used to store letter counts, as the size of the alphabet is fixed.
Solution
def shortestCompletingWord(licensePlate: str, words: List[str]) -> str:
# Step 1: Pre-process the license plate
from collections import Counter
license_count = Counter(c.lower() for c in licensePlate if c.isalpha())
# Initialize variables to track the shortest completing word
shortest_word = None
# Step 2: Iterate through each word in the list
for word in words:
word_count = Counter(word)
# Check if the current word contains all letters from the license plate with at least the same frequency
if all(word_count[letter] >= count for letter, count in license_count.items()):
# Step 3: Update the shortest completing word if necessary
if shortest_word is None or len(word) < len(shortest_word):
shortest_word = word
# Step 4: Return the result
return shortest_word
Edge Cases Handled
- Mixed Case Letters: The solution treats letters as case insensitive by converting them to lowercase.
- Non-Alphabetic Characters: Numbers and spaces in the license plate are ignored during processing.
- Multiple Shortest Words: The solution returns the first shortest completing word found, adhering to the problem’s requirement.