Problem 748

Abstract / Summary

Find the shortest word from a list that contains all the letters in a given target string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
14 lines | 512 bytes | submitted October 4, 2023 | GitHub   18% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 64% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Hash Table
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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 two a characters 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.search were 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 5 | μ = 5.33 | σ = 1.83

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
33 links | 19 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

5 easy 1 medium
7 solutions   October 4, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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