Abstract / Summary

Given a sentence and a list of words determine if the sentence can be formed by breaking it into those words.

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% (4+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Hash Table
• Memoization
• 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 solves the classic word-break problem using a depth-first search combined with memoization. A set stores the dictionary words for constant-time lookup, while a map caches the result of sub-problems indexed by the current position in the input string. The public wordBreak method prepares the data structures and launches the recursive helper dp.

Key Steps

Initialization of Data Structures

Before any recursion begins, the solution clears any previous state and populates the unordered set with the supplied dictionary. This guarantees that each call works with a fresh environment and that look-ups for dictionary words are O(1) on average.

cache.clear();
dict.clear();
for (auto w : wordDict)
    dict.insert(w);

Recursive Depth-First Search with Memoization

The core logic resides in the private dp function. It receives the original string by reference and an index indicating the start of the substring that still needs to be segmented.

The base case checks whether the index has reached the end of the string, signalling a successful segmentation.

if (index == s.size())
    return true;

If a result for the current index is already stored in cache, the function returns that cached value, avoiding repeated work.

if (cache.count(index) > 0)
    return cache[index];

The function then builds candidate words incrementally by appending one character at a time to a temporary string word. For each extension, it checks whether the constructed word exists in the dictionary. When a match is found, the function recurses on the position immediately after the matched word. A successful recursive call leads to caching true for the current index and returning immediately.

string word;
for (int i = index; i < s.size(); i++)
{
    word += s[i];
    if (dict.count(word) > 0)
        if (dp(s, i + 1))
        {
            cache[index] = true;
            return true;
        }
}

If the loop finishes without finding a valid continuation, the function records false for the current index and returns it.

cache[index] = false;
return false;

Public Interface

The wordBreak method orchestrates the process by resetting the memoization map, loading the dictionary, and invoking the recursive helper starting from position zero.

bool wordBreak(string s, vector<string>& wordDict) {
    cache.clear();
    dict.clear();
    for (auto w : wordDict)
        dict.insert(w);

    return dp(s, 0);
}

Edge Cases Handled

The algorithm gracefully handles an empty input string. The initial call to dp receives index == 0, and the base case index == s.size() immediately returns true, indicating that an empty string can be segmented trivially.

When the dictionary is empty, the loop that attempts to match words never succeeds because dict.count(word) will always be zero. Consequently, the recursion falls through to the final cache[index] = false line, correctly reporting that no segmentation is possible.

Repeated words in the dictionary do not affect correctness because the unordered set automatically eliminates duplicates during insertion, ensuring each word is stored only once.

The incremental construction of word avoids the need for substring extraction, which would otherwise create temporary objects. This approach also correctly handles words that share prefixes, as each character is added sequentially and the dictionary lookup validates the full prefix before proceeding deeper.

Performance Optimizations

The use of an unordered_set for the dictionary provides average constant-time checks for word existence, which is critical given the inner loop iterates over every possible substring starting at the current index.

Memoization via the unordered_map<int, bool> eliminates exponential blow-up by ensuring each starting index is evaluated at most once. Once a sub-problem is solved, its result is reused for any future recursive paths that encounter the same index.

Building candidate words by appending characters to a mutable string (word += s[i]) avoids repeated allocation of substrings. This in-place accumulation reduces overhead compared to repeatedly calling substr on the original string.

Clearing the cache and dict at the start of wordBreak prevents stale data from influencing new invocations, allowing the same Solution instance to be reused safely across multiple test cases without additional allocation costs.

Imagine you have a long train of colorful alphabet blocks that spell out a giant, mystery word. You also have a small box filled with smaller words that you already know, and your big job is to see if you can chop the giant word into those smaller, familiar pieces.

First, you make a quick list of all your known words so you can look them up really fast. Then, you start at the very front of the long train and grab the first letter. You add more letters one by one, checking if the group you are holding is a word from your box. If you find a match, you put a little marker down and jump to the spot right after that word to keep looking for the next piece.

Sometimes, you might get stuck and realize the road ahead does not work out. That is when you use a special notebook. If you ever reach a specific spot in the train and figure out that you cannot finish the puzzle from there, you write that down in your notebook. If you happen to visit that same spot again later, you just check your notes instead of trying the whole path all over again. You keep jumping ahead and checking your notebook until you either make it all the way to the very end of the train or run out of ways to chop it up.

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++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	C#	Java	Rust				Go	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai				Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122			C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan				Java
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
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