Python 0748.py
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
# sort letters, then regex matching
abc = re.sub("[^a-z]", "", licensePlate.lower()) # remove garbage
abc = re.compile(".*".join(sorted(list(abc))))
result = ""
for w in words:
s = "".join(sorted(list(w)))
if abc.search(s):
if result == "" or len(result) > len(w):
result = w
return result
Difficulty
and has an acceptance rate of about 64% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Hash Table
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution class implements a method that, given a license-plate string and a list of candidate words, returns the shortest word that contains all the alphabetic characters from the license plate, respecting their multiplicities. The algorithm proceeds in three logical phases: sanitizing the license plate, constructing a regular-expression pattern that encodes the required character multiset, and scanning the candidate list to locate the optimal word.
License-Plate Sanitization
The first step removes any character that is not a lower-case alphabetic letter and normalizes the case of the remaining characters. This guarantees that the subsequent matching logic works with a clean, case-insensitive representation.
abc = re.sub("[^a-z]", "", licensePlate.lower())
By applying lower() before the substitution, uppercase letters are treated identically to their lowercase counterparts. The regular-expression [^a-z] matches any character outside the range a-z, so digits, punctuation, and whitespace are stripped away. The resulting string abc contains only the letters that must appear in the completing word.
Pattern Construction
After sanitization, the algorithm builds a regular-expression pattern that enforces the presence of each required character in the correct quantity. The characters are sorted to produce a deterministic order, then interleaved with .* to allow arbitrary characters between them.
abc = re.compile(".*".join(sorted(list(abc))))
The sorted(list(abc)) call yields a list of the required letters in ascending order. Joining them with ".*" creates a pattern such as a.*b.*c for the required letters a, b, c. The leading and trailing .* are implicit because the pattern is anchored only by the characters themselves; any additional characters before, between, or after the required letters are permitted. Compiling the pattern once with re.compile avoids the overhead of recompiling it for each candidate word.
Candidate Word Evaluation
The method iterates over each word in the supplied list, transforms the word into a sorted string of its characters, and tests it against the pre-compiled pattern.
result = ""
for w in words:
s = "".join(sorted(list(w)))
if abc.search(s):
if result == "" or len(result) > len(w):
result = w
Sorting the characters of the candidate word (s) aligns its internal order with the pattern’s expected order. The search call checks whether the sorted word contains the required letters in the required multiplicities, because the pattern a.*b.*c will succeed only if each required character appears at least as many times as it occurs in abc.
When a match is found, the algorithm updates result if it is currently empty or if the newly matched word is shorter than the previously stored one. This ensures that the final returned word is the shortest among all matches. The initial empty string serves as a sentinel indicating that no match has been recorded yet.
Edge-Case Handling
The code gracefully handles several edge conditions without explicit branching:
- License plates that contain no alphabetic characters result in an empty
abc. The pattern compiled from an empty string matches any string, so the first word in the list becomes the result, satisfying the “shortest” requirement trivially. - Words that consist solely of non-alphabetic characters are still processed; sorting yields an empty string, which will only match if the required pattern is also empty.
- Duplicate letters in the license plate are preserved through sorting, so a plate like “AA12” generates a pattern
a.*a. Only words containing at least twoacharacters will satisfy the match, correctly handling multiplicities. - The case-insensitivity of the license plate is enforced by converting it to lower case, while the candidate words are left unchanged. Since the pattern operates on the sorted version of each word, any uppercase letters in the candidates are treated as distinct characters; however, the problem specification typically expects case-insensitive matching, and the current implementation implicitly assumes the input words are already lower case or that case does not affect the outcome.
Performance Optimizations
Two notable optimizations are embedded in the implementation:
- Single Compilation of the Regular Expression - By compiling the pattern once before the loop, the code eliminates the repeated parsing and compilation overhead that would occur if
re.searchwere called with a raw pattern string for each word. This reduces the per-iteration cost to a simple pattern match operation. - Sorted Representation of Words - Transforming each candidate word into a sorted string (
s) enables the regular-expression engine to perform a linear scan rather than a more complex subsequence check. The sorted form guarantees that the required characters appear in non-decreasing order, allowing the.*-joined pattern to verify presence and multiplicity with a single pass.
These choices keep the per-candidate processing time low, especially when the list of words is large, because the dominant work (sorting each word) is O(n log n) in the length of the word, and the subsequent regex search operates in linear time relative to the sorted string length. The overall design therefore scales well with both the number of candidate words and their individual lengths.
ELI5 - Simplified Explanation
Imagine a puzzle where there is a secret message full of letters hidden inside a messy license plate. The first step is to clean that plate by tossing away all the numbers and extra symbols so only the letters remain. These letters are put in alphabetical order to make them easier to track.
Then, there is a big collection of different words to check. Each word is also sorted into alphabetical order. This makes it simple to see if the letters from the license plate are hiding inside that word. If a word has every single letter needed, it gets checked to see how long it is. The goal is to find the shortest possible word that still keeps all those required letters inside. Every time a shorter word is found that works, it becomes the new winner until the very end of the list.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Rust | Python | Go | TS | |||
| LeetcodeHelp | C++ | Java | Python | ||||||
| Progiez | C++ | Java | Python | ||||||
| github | BigEggStudy | C# | |||||||
| black-shadows | C++ | ||||||||
| charles-wangkai | Java | ||||||||
| DimitrisJim | JS | ||||||||
| everthis | JS | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| zfang399 | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| BigEggStudy | C# | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| DimitrisJim | JavaScript | ||||||||
| everthis | JavaScript | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 674: Longest Continuous Increasing Subsequence
- problem 705: Design HashSet
- problem 706: Design HashMap
- problem 733: Flood Fill
- problem 747: Largest Number At Least Twice of Others
- problem 486: Predict the Winner
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality