algoadvance

The problem statement for LeetCode 748: Shortest Completing Word is as follows:

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 (ignoring numbers and case). If multiple completing words are found, return the shortest one. If there is a tie, return the first one that appears in the given array ‘words’.

Example:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"

Note:

Clarifying Questions

  1. Should we consider digits in the licensePlate for forming the completing words?
    • No, we ignore digits and special characters in licensePlate.
  2. How do we handle case sensitivity for the licensePlate?
    • Case should be ignored, meaning both ‘A’ and ‘a’ should be considered the same.
  3. What should we do if there are multiple words that are the shortest and completing?
    • Return the first one that appears in the given array words.

Strategy

  1. Extract Letters: Extract only alphabetic characters from the licensePlate and convert them to lowercase.
  2. Count Frequencies: Count the frequency of each character in the filtered licensePlate.
  3. Check Completeness: For each word in the words array:
    • Convert the word to lowercase.
    • Count the frequency of each character.
    • Check if the word contains at least the counts specified by the licensePlate frequency.
  4. Find Shortest: Keep track of the shortest completing word.

Code

Below is the Python solution to solve the problem:

from collections import Counter

def shortestCompletingWord(licensePlate, words):
    # Filter and count letters from the license plate
    license_count = Counter(char.lower() for char in licensePlate if char.isalpha())
    
    def is_completing(word):
        word_count = Counter(word)
        for char, count in license_count.items():
            if word_count[char] < count:
                return False
        return True
    
    shortest_word = None
    for word in words:
        lower_word = word.lower()
        if is_completing(lower_word):
            if shortest_word is None or len(word) < len(shortest_word):
                shortest_word = word
    
    return shortest_word

# Example usage
licensePlate = "1s3 PSt"
words = ["step", "steps", "stripe", "stepple"]
print(shortestCompletingWord(licensePlate, words)) # Output: "steps"

Time Complexity

  1. Extract Letters: O(n) where n is the length of licensePlate.
  2. Count Frequencies: O(m) where m is the total number of characters in the words list.
  3. Check Completeness: For each word (assuming there are w words each of maximum length l), it takes O(l) to check frequency completeness.
  4. Find Shortest: O(w * l) due to iterating through all words and comparing lengths.

Overall, the complexity is O(n + m + w*l), which can be approximated as O(w*l) in scenarios where the length of licensePlate and the number of words is significantly smaller compared to the total characters in all words combined.

Try our interview co-pilot at AlgoAdvance.com