Abstract / Summary

Check if all words in one list have prefixes that match any word in another list.

Note

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

This problem is ranked as

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

Typical patterns to solve this problem:

• Array
• String
• String Matching
• Trie
• Two Pointers

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.

Overview

The provided implementation solves the “camel case matching” problem by translating the input pattern into a regular-expression that captures the allowed structure of each query string. The method then applies this expression to every element of queries, producing a Boolean result that indicates whether the query conforms to the camel-case constraints defined by the pattern.

Construction of the Regular Expression

The core of the algorithm is the creation of a pattern that permits any number of lowercase letters before, between, and after the characters of the original pattern. This is achieved by initializing a string with a start-anchor and a segment that matches zero or more lowercase letters:

regex = "^[a-z]*"

A loop iterates over each character p in the supplied pattern. For each character the algorithm appends the literal character itself followed by a segment that again matches zero or more lowercase letters. The loop body is:

for p in pattern:
    regex += p
    regex += "[a-z]*"

After processing all characters, a terminating end-anchor is added to ensure the entire query string is examined:

regex += "$"

The resulting regex string embodies the rule that uppercase letters must appear in the exact order of pattern, while any number of lowercase letters may be interleaved.

Application to the Query List

With the regular expression prepared, the method iterates over the list queries. For each query q it invokes Python’s built-in regular-expression matcher:

for q in queries:
    yield re.match(regex, q) != None

The expression re.match(regex, q) != None evaluates to True when the query satisfies the constructed pattern and False otherwise. By using yield, the function produces a generator that streams Boolean results in the same order as the input queries.

Edge-Case Handling

The design implicitly accommodates several edge conditions:

• Empty pattern - When pattern is an empty string, the loop that appends characters does not execute. The resulting regular expression becomes "^[a-z]*$", which matches any string consisting solely of lowercase letters (including the empty string). Queries containing uppercase letters will fail, satisfying the camel-case rule that no uppercase letters are allowed when the pattern is empty.

• Queries shorter than the pattern - Because each character of pattern is required to appear in the regex, any query lacking one of those characters will not match. The regular expression enforces the presence of every pattern character in order, so shorter queries automatically yield False.

• Extra uppercase letters in queries - The regex permits only the uppercase letters that appear in pattern. Any additional uppercase character in a query will break the match because the expression does not contain a wildcard for uppercase letters. Consequently, queries with stray uppercase letters are correctly rejected.

• All-lowercase queries - When a query contains only lowercase letters, the regex matches if and only if the pattern itself is empty. For non-empty patterns, the required uppercase characters are missing, leading to a False result.

Performance Optimizations

The implementation exhibits a few performance-focused choices:

• Single regex construction - The regular expression is assembled once before the loop over queries. This avoids repeated string concatenation or pattern compilation for each query, reducing overhead proportional to the number of queries.

• Leverage of the C-implemented re engine - By delegating the matching work to Python’s standard re module, the code benefits from the highly optimized, compiled regular-expression engine written in C. This typically outperforms a pure-Python character-by-character comparison, especially for long query strings.

• Generator output - Using yield creates a lazy generator rather than materializing an intermediate list of Boolean values. This can lower memory consumption when the caller consumes results incrementally, as only one Boolean value needs to be held in memory at a time.

Overall, the solution translates the problem into a concise regular-expression formulation, builds the expression efficiently, and relies on the underlying engine for fast matching while providing results in a memory-friendly streaming fashion.

Imagine a group of secret codes written in a special way where every time a capital letter appears, it is like a little flag marking the start of a new, hidden word. This code looks at a big list of these words and checks if they match a specific secret pattern.

First, the computer takes the pattern and turns it into a magical rule. It says that between every letter in the pattern, there can be any number of small, lowercase letters. It also says the word must start and end exactly how the pattern describes. This magical rule acts like a filter or a sieve.

Then, the computer looks at every word in the list one by one. It puts each word through the magical rule sieve. If the word fits perfectly into the pattern, the computer remembers that it is a match. If the word has extra big letters in the wrong places or misses some of the required letters, it does not fit the pattern at all. After checking all of them, the computer has a final list of which words matched the pattern and which ones did not.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Python	C++		Java				TS
	WalkCCC	Python	C++		Java
	leetcode.ca	Python	C++		Java			Go	TS
	LeetcodeHelp	Python	C++		Java
	Progiez	Python	C++		Java
github	black-shadows		C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq		C++
	Garvit244	Python
	JoshCrozier			JS
	lkwq007	Python
	suxrobGM						C#
	trung-hn	Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
Garvit244	Python
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

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