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'.
def count(word):
counter = [0] * 26
for c in word:
counter[ord(c) - ord('a')] += 1
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
.
def check(counter1, counter2):
for i in range(26):
if counter1[i] > counter2[i]:
return False
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.
counter = count(c.lower() for c in licensePlate if c.isalpha())
ans, n = None, 16
for word in words:
if n <= len(word):
continue
t = count(word)
if check(counter, t):
n = len(word)
ans = word
The process for each word in the loop is as follows:
- We skip the word if its length is not less than the current shortest completing word's length (
n
) to optimize performance. - We generate a frequency array of the word (
t
) usingcount
. - We use
check
to see ift
meets the requirements compared tocounter
, which is the frequency array forlicensePlate
. - If it does, this is the new shortest completing word, and we update
ans
with this word andn
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
1class Solution:
2 def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
3
4 # Helper function to count the frequency of each letter in a word.
5 def count_letters(word):
6 # Initialize a counter for 26 letters of the alphabet.
7 counter = [0] * 26
8 # Increment the letter's corresponding counter.
9 for char in word:
10 counter[ord(char) - ord('a')] += 1
11 return counter
12
13 # Helper function to check if the word contains all the
14 # needed letters with required frequency.
15 def contains_needed_letters(license_counter, word_counter):
16 # Iterate through each letter in the alphabet.
17 for i in range(26):
18 # If the license has more letters than the word,
19 # then it's not a completing word.
20 if license_counter[i] > word_counter[i]:
21 return False
22 return True
23
24 # Transforms the license plate into lowercase and filters out non-alphabetic characters.
25 # Then, counts the frequency of each letter in the license plate.
26 license_counter = count_letters(char.lower() for char in licensePlate if char.isalpha())
27
28 # Initialize the variables for tracking the shortest completing word.
29 shortest_completing_word = None
30 min_length = 16 # Given constraint - words length doesn't exceed 15.
31
32 # Iterate through the words list to find the shortest completing word.
33 for word in words:
34 # Skip the iteration if the current word is not shorter than min_length.
35 if min_length <= len(word):
36 continue
37 # Count the frequency of letters in the current word.
38 word_counter = count_letters(word)
39 # Check if the current word has all the required letters
40 # with at least the frequencies in the license plate.
41 if contains_needed_letters(license_counter, word_counter):
42 # Update min_length and shortest_completing_word with the current word's length and the word itself.
43 min_length = len(word)
44 shortest_completing_word = word
45
46 return shortest_completing_word
47
1class Solution {
2 // Finds the shortest completing word in words that covers all letters in licensePlate
3 public String shortestCompletingWord(String licensePlate, String[] words) {
4 // Count the frequency of letters in the license plate, ignoring case and non-letters
5 int[] licensePlateCounter = countLetters(licensePlate.toLowerCase());
6
7 // Initialize the answer variable to hold the shortest completing word
8 String shortestCompletingWord = null;
9
10 // Initialize the shortest length found so far to an upper bound
11 int minLength = 16; // As per the problem, words are at most 15 letters long
12
13 // Iterate through each word in the array
14 for (String word : words) {
15 // Skip the word if its length is not less than the shortest length found so far
16 if (minLength <= word.length()) {
17 continue;
18 }
19
20 // Count the frequency of letters in the current word
21 int[] wordCounter = countLetters(word);
22
23 // Check if the current word covers all letters in the license plate
24 if (doesWordCoverLicensePlate(licensePlateCounter, wordCounter)) {
25 // Update the shortest completing word and the minimum length found so far
26 minLength = word.length();
27 shortestCompletingWord = word;
28 }
29 }
30
31 // Return the shortest completing word found
32 return shortestCompletingWord;
33 }
34
35 // Counts the frequency of each letter in a given word
36 private int[] countLetters(String word) {
37 int[] letterCounter = new int[26];
38 // Iterate through each character in the word
39 for (char c : word.toCharArray()) {
40 // Increment the counter for the letter if it's a letter
41 if (Character.isLetter(c)) {
42 letterCounter[c - 'a']++;
43 }
44 }
45 return letterCounter;
46 }
47
48 // Checks if wordCounter covers all the letters in licensePlateCounter
49 private boolean doesWordCoverLicensePlate(int[] licensePlateCounter, int[] wordCounter) {
50 // Iterate over each letter count
51 for (int i = 0; i < 26; ++i) {
52 // If the current letter's count in licensePlateCounter exceeds that in wordCounter,
53 // the word does not cover the license plate, return false
54 if (licensePlateCounter[i] > wordCounter[i]) {
55 return false;
56 }
57 }
58 // If all letter counts are covered, return true
59 return true;
60 }
61}
62
1#include <string>
2#include <vector>
3#include <cctype> // For isalpha and tolower
4
5class Solution {
6public:
7 // Finds the shortest word in 'words' that contains all the letters in 'licensePlate'
8 string shortestCompletingWord(string licensePlate, vector<string>& words) {
9 // Count the frequency of each letter in the license plate
10 vector<int> licenseCounter = countLetters(licensePlate);
11 int minLength = INT_MAX;
12 string shortestWord;
13
14 // Iterate over each word in the list
15 for (auto& word : words) {
16 // If current word is longer than the shortest found, skip it
17 if (minLength <= word.size()) continue;
18
19 // Count the frequency of each letter in the word
20 vector<int> wordCounter = countLetters(word);
21
22 // Check if the word contains all letters in the license plate
23 if (containsAllLetters(licenseCounter, wordCounter)) {
24 // Update minimum length and answer if this word is shorter
25 minLength = word.size();
26 shortestWord = word;
27 }
28 }
29 return shortestWord;
30 }
31
32private:
33 // Counts the frequency of each letter in a word
34 vector<int> countLetters(string& word) {
35 vector<int> counter(26, 0); // Initiate a counter for 26 letters
36
37 // Increment the count for each letter in the word
38 for (char& c : word) {
39 if (isalpha(c)) {
40 ++counter[tolower(c) - 'a'];
41 }
42 }
43 return counter;
44 }
45
46 // Checks if 'counterSource' contains at least as many of each letter as 'counterTarget'
47 bool containsAllLetters(vector<int>& counterSource, vector<int>& counterTarget) {
48 for (int i = 0; i < 26; ++i) {
49 // If the target has more of a letter than the source, return false
50 if (counterSource[i] > counterTarget[i]) {
51 return false;
52 }
53 }
54 // If the source contains at least as many of each letter, return true
55 return true;
56 }
57};
58
1function shortestCompletingWord(licensePlate: string, words: string[]): string {
2 // Count the frequency of each letter in the license plate
3 const licenseCounter: number[] = countLetters(licensePlate);
4 let minLength: number = Number.MAX_SAFE_INTEGER;
5 let shortestWord: string = '';
6
7 // Iterate over each word in the list
8 for (let word of words) {
9 // If the current word is longer than the shortest so far, skip it
10 if (minLength <= word.length) continue;
11
12 // Count the frequency of each letter in the current word
13 const wordCounter: number[] = countLetters(word);
14
15 // Check if the word contains all the letters in the license plate
16 if (containsAllLetters(licenseCounter, wordCounter)) {
17 // Update minimum length and shortest word if this word is shorter
18 minLength = word.length;
19 shortestWord = word;
20 }
21 }
22 return shortestWord;
23}
24
25// Helper function to count the frequency of each letter in a word
26function countLetters(word: string): number[] {
27 const counter: number[] = new Array(26).fill(0); // Initialize a counter for 26 letters
28
29 // Increment the count for each alphabet letter in the word
30 for (let char of word) {
31 if (isAlphabetic(char)) {
32 counter[char.toLowerCase().charCodeAt(0) - 'a'.charCodeAt(0)]++;
33 }
34 }
35 return counter;
36}
37
38// Helper function to verify if sourceCounter contains at least
39// as many of each letter as targetCounter
40function containsAllLetters(sourceCounter: number[], targetCounter: number[]): boolean {
41 for (let i = 0; i < 26; ++i) {
42 // If the target has more of any particular letter than the source, return false
43 if (sourceCounter[i] < targetCounter[i]) {
44 return false;
45 }
46 }
47 // If source contains at least as many of each letter, return true
48 return true;
49}
50
51// Helper function to check if a character is an alphabetic letter
52function isAlphabetic(char: string): boolean {
53 const code: number = char.charCodeAt(0);
54 return (code >= 65 && code <= 90) || (code >= 97 && code <= 122); // A-Z or a-z
55}
56
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 ofO(k)
wherek
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 normalizedlicensePlate
once, resulting in a time complexity ofO(m)
wherem
is the number of alphabetic characters inlicensePlate
. - For each word in
words
, thecount
function is called again, giving a time complexity ofO(k * n)
wheren
is the number of words andk
is the average length of the words. - The function
check
has a time complexity ofO(1)
because it checks a fixed size array (26 letters of English alphabet). - Since
check
is called for every word, we multiply it byn
, 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 occupyO(1)
space. - The space used to store the answer and the length of the shortest word found so far (
n
andans
) isO(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.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!