#748

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Shortest Completing Word

Find the shortest word that completes the license plate by matching all required letters, considering frequency and case insensitivity.

array hash table string

Problem Statement

You are given a string licensePlate and an array of strings words. Your task is to find the shortest word in words that contains all the letters in licensePlate. Ignore any numbers and spaces in the licensePlate, and treat the letters case insensitively. Each letter must appear in the word as often as it does in the license plate. If a letter appears multiple times in the license plate, the word must have at least the same number of occurrences.

For example, if licensePlate = "aBc 12c", the word must contain at least one 'a', one 'b', and two 'c's. Your goal is to identify the shortest word in the list of words that satisfies this condition.

Examples

Example 1

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

Output: "steps"

licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'. "step" contains 't' and 'p', but only contains 1 's'. "steps" contains 't', 'p', and both 's' characters. "stripe" is missing an 's'. "stepple" is missing an 's'. Since "steps" is the only word containing all the letters, that is the answer.

Example 2

Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]

Output: "pest"

licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.

Constraints

1 <= licensePlate.length <= 7
licensePlate contains digits, letters (uppercase or lowercase), or space ' '.
1 <= words.length <= 1000
1 <= words[i].length <= 15
words[i] consists of lower case English letters.

Solution Approach

Frequency Count of Letters

Start by counting the frequency of each letter in the licensePlate, ignoring spaces and numbers. Convert all characters to lowercase to ensure case insensitivity.

Filter Words with Letter Count Matching

For each word in the list, count the frequency of each letter and check if it contains all the letters from the licensePlate with at least the same frequency. If it does, consider it a potential match.

Select the Shortest Matching Word

Out of the valid words, select the one that is the shortest. If multiple words have the same length, the first one encountered should be chosen.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach depends on the number of words and their lengths. Checking the frequency of each letter in a word takes linear time relative to its length. Therefore, the overall time complexity is O(n * m), where n is the number of words and m is the average length of the words. The space complexity is O(k), where k is the number of unique letters in the licensePlate (which is at most 26).

What Interviewers Usually Probe

The candidate effectively counts letter frequencies in both the license plate and words.
The candidate optimizes the solution by focusing on the shortest word after filtering.
The candidate handles edge cases such as multiple matches or no match gracefully.

Common Pitfalls or Variants

Common pitfalls

Ignoring letter frequencies and only checking for presence rather than count.
Not converting letters to lowercase, which could lead to incorrect comparisons.
Failing to consider spaces and numbers in the license plate properly.

Follow-up variants

Modify the problem to consider only words with exactly the same length as the shortest word.
Consider a variant where the words are in sorted order and the first valid word should be returned.
Change the problem to find the longest word that matches the license plate.

FAQ

How do I handle case sensitivity in the Shortest Completing Word problem?

You should treat all letters as case insensitive, which means converting both the license plate and words to lowercase before counting the frequency of letters.

What should I do if there are multiple valid words of the same length?

If multiple words match, the first valid word that appears should be selected. The problem specifically asks for the shortest word.

Can the words contain numbers or spaces in the Shortest Completing Word problem?

No, only letters should be considered when matching the license plate. You should ignore numbers and spaces in the license plate and the words.

What happens if no word matches the license plate?

The problem guarantees that at least one word will match, so you do not need to handle cases with no valid matches.

How does the 'frequency count' approach help in solving this problem?

Counting the frequency of letters ensures that we account for how many times each letter appears in the license plate and that the word we select contains at least as many occurrences of each letter.

terminal

Solution

Solution 1: Counting

First, we use a hash table or an array $cnt$ of length $26$ to count the frequency of each letter in the string `licensePlate`. Note that we convert all letters to lowercase for counting.

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        cnt = Counter(c.lower() for c in licensePlate if c.isalpha())
        ans = None
        for w in words:
            if ans and len(w) >= len(ans):
                continue
            t = Counter(w)
            if all(v <= t[c] for c, v in cnt.items()):
                ans = w
        return ans

Continue Practicing

#745 prefix and suffix search #752 open the lock #721 accounts merge