748. Shortest Completing Word

Problem Description

In this LeetCode problem, we are given a string licensePlate and an array of strings words. Our task is to find the shortest word in words that contains all the letters in licensePlate, disregarding any numbers and spaces, and treating letters as case-insensitive. Notably, if a letter repeats in the licensePlate, it must appear at least as many times in the word. The essence of the problem is to identify the most concise word from an array that encapsulates all alphabetic characters of the given license plate string.

Intuition

To arrive at the solution for this problem, we breakdown the requirements into smaller steps and handle each part. First, we create a function called count that converts a given word into a frequency array that represents how many times each letter appears in the word.

Once we have count, we need a way to determine if a word in words can be considered a "completing word". To do this, we craft a check function that compares two frequency arrays: one from the cleaned licensePlate and one from a candidate word. The check function goes over each letter's frequency and ensures the candidate word has equal or more occurrences of each letter found in licensePlate.

Then we iterate over each word in words and apply the count function to it. If it passes the check with the licensePlate's frequency array, it means we've found a potential completing word. We maintain a variable for the shortest word found (ans) and its length (n). If a new completing word is shorter than the current best, we update ans with this new word.

This way, by prioritizing words that meet the completing criteria and are shorter than any others we've seen, we can solve the problem effectively.

Solution Approach

The solution approach for finding the shortest completing word involves the use of frequency arrays and efficient checks for each word in the words array against the licensePlate. Here's a step-by-step explanation of the implementation:

The count function

We define a count function that takes a word and transforms it into a frequency array, which is an array of 26 integers (corresponding to the 26 letters of the English alphabet), each element representing the count of a specific letter from 'a' to 'z'. The ord function is used to get the ASCII value of a character, and we subtract the ASCII value of 'a' to map 'a' to index 0, 'b' to index 1, and so on up to 'z'.

1def count(word):
2    counter = [0] * 26
3    for c in word:
4        counter[ord(c) - ord('a')] += 1
5    return counter

The check function

The check function compares two frequency arrays: one from the license plate (counter1) and the other from the current word (counter2). If for any letter the count in the license plate is greater than the count in the word, check returns False indicating that the word is not a completing word. Otherwise, if all letter counts are equal or higher in the word than in the license plate, it returns True.

1def check(counter1, counter2):
2    for i in range(26):
3        if counter1[i] > counter2[i]:
4            return False
5    return True

The main loop

The main part of the algorithm is a loop through each word in words. It initializes two variables: ans, to store the currently found shortest completing word, and n, to store its length.

1counter = count(c.lower() for c in licensePlate if c.isalpha())
2ans, n = None, 16
3for word in words:
4    if n <= len(word):
5        continue
6    t = count(word)
7    if check(counter, t):
8        n = len(word)
9        ans = word

The process for each word in the loop is as follows:

1. We skip the word if its length is not less than the current shortest completing word's length (n) to optimize performance.
2. We generate a frequency array of the word (t) using count.
3. We use check to see if t meets the requirements compared to counter, which is the frequency array for licensePlate.
4. If it does, this is the new shortest completing word, and we update ans with this word and n with its length.

The loop proceeds until all words have been checked, and the shortest completing word (ans) is returned as the answer.

This algorithm effectively leverages data structures (arrays) and functions to compare character frequencies, significantly simplifying and optimizing the process of determining completing words.

Example Walkthrough

To illustrate the solution approach, let's take a small example. Suppose licensePlate is "aBc 1123" and words is ["step", "steps", "stripe", "stepple"].

The first step would be to create a frequency array for the cleaned licensePlate, which disregards numbers and spaces and is case-insensitive. This means "aBc" becomes "abc" and our count function generates an array [1, 1, 1, 0, ..., 0], indicating that there's one 'a', one 'b', and one 'c'.

Iterating Over Each Word

We then iterate over each word in words and check if it's a completing word for licensePlate.

• For "step", we get the frequency array [0, 0, 0, 0, 1, 0, ..., 1], which has an 'e' and a 'p', but lacks 'a' and 'b'.
• For "steps", the frequency array is [0, 0, 0, 0, 1, 0, ..., 1, 1]. This word also covers 's', but still misses 'a' and 'b'.
• "stripe" has a frequency array [0, 0, 0, 0, 1, 0, ..., 1, 1, 1], containing 'e', 'p', 'r', 's', 't', and 'i', and it does have at least one 'a', 'b', and 'c'.
• Finally, "stepple" has the array [0, 0, 0, 0, 1, 0, ..., 2, 2, 1], where there is more than one occurrence of some letters, but it's longer than "stripe".

Through our check function, we see that only "stripe" has equal or more occurrences of the letters in licensePlate, which are 'a', 'b', and 'c', so it is a potential completing word.

Finding the Shortest Completing Word

Since "stripe" is shorter than "stepple" and it contains all the required letters (ignoring the unnecessary 'i', 'r', and 't'), "stripe" becomes our ans and its length, 6, becomes n.

As no other word in words is both a completing word for "aBc 1123" and shorter than "stripe", "stripe" is the answer we return. It successfully encapsulates all alphabetic characters of the license plate "aBc 1123" in the most concise form found in the list words.

This example demonstrates how the count and check functions, together with an iterating loop, can be used to efficiently solve the problem.

Solution Implementation

Time and Space Complexity

The time complexity of the shortestCompletingWord function primarily depends on two factors: the number of words in the input words list and the average length of each word. Here is the breakdown:

• The count function has a time complexity of O(k) where k is the length of the word. It iterates once through all the characters of the word.
• This count function is called for every character in the normalized licensePlate once, resulting in a time complexity of O(m) where m is the number of alphabetic characters in licensePlate.
• For each word in words, the count function is called again, giving a time complexity of O(k * n) where n is the number of words and k is the average length of the words.
• The function check has a time complexity of O(1) because it checks a fixed size array (26 letters of English alphabet).
• Since check is called for every word, we multiply it by n, but it doesn't affect the overall time complexity significantly due to the constant size.

Combining the above steps, the total time complexity for the function is O(m + k * n).

The space complexity is determined by:

• The counter arrays used to store character frequencies for the licensePlate and each word. Since these are of fixed size (26), they occupy O(1) space.
• The space used to store the answer and the length of the shortest word found so far (n and ans) is O(1).

Thus, the overall space complexity is O(1) because it does not scale with the size of the input.

In summary:

• Time Complexity: O(m + k * n)
• Space Complexity: O(1)

Learn more about how to find time and space complexity quickly using problem constraints.