We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Completing Word

Difficulty: Easy

Problem Description

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.

Key Insights

  • A completing word must contain all required letters from the licensePlate, considering their frequency.
  • Non-letter characters in licensePlate should be ignored.
  • The search needs to find the shortest word that matches the criteria.
  • If multiple shortest completing words exist, the first one in the input list should be returned.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of words and m is the maximum length of a word. Space Complexity: O(1), as the frequency counts for the letters are fixed (only 26 letters).

Solution

To solve the problem, we can use the following approach:

  1. Create a frequency count of the letters needed from the licensePlate, ignoring non-letter characters and treating letters case insensitively.
  2. Iterate through each word in the words array and check if it contains all the letters with the required frequencies using the frequency count.
  3. Keep track of the shortest completing word found during the iteration.
  4. Return the first shortest completing word encountered.

The primary data structure used is a frequency counter (like a dictionary or array) to store the required letters and their counts from the licensePlate. For each word, we'll compare its letter counts against the required counts.

Code Solutions

from collections import Counter

def shortestCompletingWord(licensePlate, words):
    # Create a frequency count of the letters in the licensePlate
    letter_count = Counter(char.lower() for char in licensePlate if char.isalpha())
    
    # Initialize variables to track the shortest completing word
    shortest_word = None
    
    for word in words:
        # Create a frequency count of the letters in the current word
        word_count = Counter(word)
        
        # Check if the word meets the completing word criteria
        if all(word_count[char] >= count for char, count in letter_count.items()):
            # Update the shortest word if necessary
            if shortest_word is None or len(word) < len(shortest_word):
                shortest_word = word
    
    return shortest_word
← Back to All Questions