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.
For example, if licensePlate = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".
Return the shortest completing word in words. It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.
Example 1:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps" Explanation: 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" Explanation: 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 <= 7licensePlate contains digits, letters (uppercase or lowercase), or space ' '.1 <= words.length <= 10001 <= words[i].length <= 15words[i] consists of lower case English letters.Problem Overview: You receive a licensePlate string containing letters, digits, and spaces, plus a list of candidate words. The goal is to return the shortest word that contains every letter from the license plate with at least the same frequency, ignoring case and non‑letter characters.
Approach 1: Counting Letters and Validating Words (O(n * m) time, O(1) space)
This approach treats the problem as a frequency matching task. First iterate through licensePlate and build a fixed-size frequency array of 26 characters for required letters. Ignore digits and spaces, and convert everything to lowercase. Then iterate through each word in the list and compute its own frequency count. Compare the word's counts with the required counts. If the word satisfies every letter requirement, it is a valid completing word. Track the shortest valid candidate while scanning. The constant-sized frequency array keeps space complexity at O(1), and the algorithm performs straightforward scans over each word. This solution heavily uses ideas from hash table style frequency counting and basic string processing.
Approach 2: Using Regular Expressions and Sets (O(n * m) time, O(k) space)
This variant builds validation logic using pattern matching instead of explicit frequency arrays. Extract all letters from licensePlate, normalize them to lowercase, and derive constraints that each candidate word must satisfy. Regular expressions with repeated lookaheads can enforce that required letters exist the needed number of times. Each word is then tested against this compiled pattern. A set can help track unique letters when constructing constraints, while repeated characters must still be encoded in the regex pattern. While the asymptotic time complexity remains O(n * m), regex engines introduce additional constant overhead compared to simple counting. This technique may appeal when your environment already relies heavily on pattern matching logic or when you want a compact validation step.
Recommended for interviews: The counting approach is what interviewers typically expect. It demonstrates understanding of frequency counting, efficient iteration, and constant‑space optimization using a fixed 26‑character array. The regex approach works but hides the core algorithmic idea behind pattern matching. Showing the counting solution first proves you can translate the problem into a clear constraint check using basic array operations.
In this approach, we focus on counting the frequency of each letter in the licensePlate and then check for each word in the words list whether it completes these letters with equal or more frequency.
Steps:
The solution uses Python's collections.Counter to count the frequency of the alphabetic characters in the licensePlate string and the words list. For each word, it checks if every character in the licensePlate exists in the word with at least the same frequency.
Python
JavaScript
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(k), where k is the number of unique alphabetic characters in the licensePlate.
This approach involves using regular expressions to extract letters from licensePlate and using sets to check the presence of required characters in words.
Steps:
The Java solution utilizes arrays to count character frequencies. It processes the licensePlate to filter out alphabetic characters, and for each word, checks if it can complete the character counts from the licensePlate.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), apart from input storage, we only use fixed size frequency arrays.
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.
Then, we traverse each word w in the array words. If the length of the word w is longer than the length of the answer ans, we directly skip this word. Otherwise, we use another hash table or an array t of length 26 to count the frequency of each letter in the word w. If for any letter, the frequency of this letter in t is less than the frequency of this letter in cnt, we can also directly skip this word. Otherwise, we have found a word that meets the conditions, and we update the answer ans to the current word w.
The time complexity is O(n times |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the array words, and \Sigma is the character set. In this case, the character set is all lowercase letters, so |\Sigma| = 26.
| Approach | Complexity |
|---|---|
| Counting Letters and Validating Words | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Using Regular Expressions and Sets | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Letters and Validating Words | O(n * m) | O(1) | Best general solution. Fast, simple, and interview friendly. |
| Regular Expressions and Sets | O(n * m) | O(k) | Useful when pattern matching tools are preferred or already used in the codebase. |
花花酱 LeetCode 748. Shortest Completing Word - 刷题找工作 EP138 • Hua Hua • 2,462 views views
Watch 9 more video solutions →Practice Shortest Completing Word with our built-in code editor and test cases.
Practice on FleetCode