Abstract / Summary

Given a list of words check if any word can be formed by concatenating other words from the same 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 50% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Depth First Search
• Dynamic Programming
• Sorting
• String
• Trie

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 defines a Solution class with a method findAllConcatenatedWordsInADict. The method receives a list of strings and returns those strings that can be formed by concatenating at least two other words from the same list. The algorithm relies on a depth-first search with memoization to explore possible segmentations of each word while preventing a word from matching itself.

Key Steps

The first step creates a hash-based container for constant-time membership checks.

all = set(words)

A nested helper function deeper is declared with an lru_cache decorator to store intermediate results.

@lru_cache(maxsize = 10000)
def deeper(w, first):
    if w in all and not first:  # prevent self-match
        return True

    for i in range(1, len(w)):
        if w[:i] in all and deeper(w[i:], False):
            return True
    return False

The helper receives the current substring w and a boolean flag first indicating whether the call originates from the top-level word. The base case checks whether the substring exists in the original set and ensures that the match is not the original word itself. The loop iterates over every possible split position, testing whether the left part is a known word and recursively verifying that the right part can be segmented.

Finally, a list comprehension filters the original list, retaining only those words for which the recursive check succeeds.

return [ w for w in words if deeper(w, True) ]

Edge Cases Handled

The condition if w in all and not first explicitly excludes the scenario where a word would be considered a concatenation of itself, thereby handling the self-match edge case. When a word is empty, the loop range range(1, len(w)) yields no iterations, and the function returns False, correctly excluding empty strings from the result. Duplicate entries in the input list are collapsed by the set conversion, ensuring that repeated words do not affect the lookup logic. Single-character words are processed without error; they either match directly (but are rejected by the first flag) or fail to produce any valid split, leading to a False outcome.

Performance Optimizations

The conversion of the input list to a set provides O(1) average-case lookups for word existence checks, which is critical given the repeated membership tests inside the recursion. Memoization via lru_cache stores the result of each distinct (w, first) pair, preventing exponential recomputation of overlapping subproblems. The early return when a valid split is found (return True) avoids unnecessary exploration of remaining split positions. The recursion depth is bounded by the length of the word, and the cache size limit (maxsize = 10000) balances memory usage against the benefit of reusing results for frequently encountered substrings.

Imagine you have a giant collection of building blocks, and each block is a word. Some blocks are small, like cat, and some are bigger, like dog. You want to see if you can build a large word by stacking together smaller words that are already in your collection.

First, the code makes a special list called a set so it can check if a word exists really quickly, just like having a magical magnifying glass to look through a toy box.

Then, there is a helper function called deeper that acts like a game inspector. When the inspector looks at a big word, it tries to chop the word into little pieces. It checks if the first piece is a word from your collection, and then it asks a secret question to see if the rest of the word is also made of other words from the collection.

The inspector is very smart because it remembers the answers to words it has already looked at, so it does not have to do the same work twice. If it successfully chops the word into smaller pieces that are all in the collection, then that word is special.

Finally, the code goes through every word in the list and asks the inspector to check them one by one. If the inspector says yes, that word gets saved to a new list because it is made of other smaller words.

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

not analyzed yet

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					Go	Python
	LeetcodeHelp	C++	Java						Python
	MemoryLimitExceeded	C++							Python
	Progiez	C++	Java						Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	gouthampradhan		Java
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	ruoru					Rust
	suxrobGM				C#
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

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