Domain 1EasyCORE

Shortest Completing Word

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

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 words array that contains all the letters in licensePlate.

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

  1. 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.
  2. Iterate Through Words:

    • For each word in the words list, 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.
  3. 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.
  4. 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.