Word Break asks: can the string split entirely into dictionary words? DP over positions + trie walks instead of substring hashing.
Focus on recognizing:
“Split into dictionary words” → dp[i] true ⇒ walk trie from i
Pattern 1: Word Break
Segmenting "leetcode" into leet | code — each true dp[i] launches one trie walk. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Word Break (DP + Trie)
Decide whether a string can be segmented into dictionary words, using a trie to test starts-at-every-index.
dp[i] marks that s[0..i) is segmentable. From each true dp[i], walk the trie along s[i..]; whenever a word-end is hit at j, set dp[j] = true. dp[n] gives the answer.
1
dp[0] = true
2
for i in 0..n-1 where dp[i]:
3
walk trie from i collecting words
4
on word end at j: dp[j] = true
5
return dp[n]
public boolean wordBreak(String s, List<String> wordDict) {
// build trie once
TrieNode root = new TrieNode();
for (String w : wordDict) root.insert(w);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true; // empty prefix
for (int i = 0; i < n; i++) {
if (!dp[i]) continue; // no chain reaches here
TrieNode cur = root;
for (int j = i; j < n; j++) {
cur = cur.children[s.charAt(j) - 'a'];
if (cur == null) break; // dead end in trie
if (cur.isEnd) dp[j + 1] = true;
}
}
return dp[n];
}def word_break(s, word_dict):
# build trie once
root = {}
END = "$"
for w in word_dict:
cur = root
for ch in w:
cur = cur.setdefault(ch, {})
cur[END] = True
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty prefix
for i in range(n):
if not dp[i]:
continue # no chain reaches here
cur = root
for j in range(i, n):
cur = cur.get(s[j])
if cur is None:
break # dead end in trie
if END in cur:
dp[j + 1] = True
return dp[n]struct TrieNode {
TrieNode* children[26] = {};
bool isEnd = false;
void insert(const string& w) {
TrieNode* cur = this;
for (char c : w) {
auto& next = cur->children[c - 'a'];
if (!next) next = new TrieNode();
cur = next;
}
cur->isEnd = true;
}
};
bool wordBreak(string s, vector<string>& wordDict) {
TrieNode root;
for (string& w : wordDict) root.insert(w);
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true; // empty prefix
for (int i = 0; i < n; i++) {
if (!dp[i]) continue; // no chain reaches here
TrieNode* cur = &root;
for (int j = i; j < n; j++) {
cur = cur->children[s[j] - 'a'];
if (!cur) break; // dead end in trie
if (cur->isEnd) dp[j + 1] = true;
}
}
return dp[n];
}function wordBreak(s, wordDict) {
const root = {};
const END = "$";
for (const w of wordDict) {
let cur = root;
for (const ch of w) cur = cur[ch] ??= {};
cur[END] = true;
}
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true; // empty prefix
for (let i = 0; i < n; i++) {
if (!dp[i]) continue; // no chain reaches here
let cur = root;
for (let j = i; j < n; j++) {
cur = cur[s[j]];
if (!cur) break; // dead end in trie
if (cur[END]) dp[j + 1] = true;
}
}
return dp[n];
}
dp[i]means “prefix of length i splits cleanly”. Every true cell seeds a fresh trie walk.
Pattern 2: Return One Segmentation
DFS with memoized failed starts records its successful cuts.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Word Break — Reconstruct One Split
Find one way to split a string into dictionary words using a trie-guided DFS with memoization.
From each position, walk the trie along the remaining characters; at every word-end, recurse from the next index. Memoize failed starts so identical suffixes aren't re-walked.
1
dfs(i): if i == len → success
2
walk trie from root along s[i…]
3
at each isEnd: dfs(j + 1)
4
memo failed starts
Track predecessors to rebuild an actual split:
public List<String> wordBreakPath(String s, List<String> dict) {
TrieNode root = new TrieNode();
for (String w : dict) root.insert(w);
int n = s.length();
boolean[] dp = new boolean[n + 1];
int[] prev = new int[n + 1]; // where this segment started
Arrays.fill(prev, -1);
dp[0] = prev[0] = 0;
for (int i = 0; i < n; i++) {
if (!dp[i]) continue;
TrieNode cur = root;
for (int j = i; j < n; j++) {
cur = cur.children[s.charAt(j) - 'a'];
if (cur == null) break;
if (cur.isEnd && !dp[j + 1]) {
dp[j + 1] = true;
prev[j + 1] = i; // remember chain link
}
}
}
LinkedList<String> parts = new LinkedList<>();
for (int at = n; at > 0; ) {
int start = prev[at];
parts.addFirst(s.substring(start, at));
at = start;
}
return dp[n] ? parts : Collections.emptyList();
}from collections import deque
def word_break_path(s, word_dict):
root = {}
END = "$"
for w in word_dict:
cur = root
for ch in w:
cur = cur.setdefault(ch, {})
cur[END] = True
n = len(s)
dp = [False] * (n + 1)
prev = [-1] * (n + 1) # where this segment started
dp[0] = True
prev[0] = 0
for i in range(n):
if not dp[i]:
continue
cur = root
for j in range(i, n):
cur = cur.get(s[j])
if cur is None:
break
if END in cur and not dp[j + 1]:
dp[j + 1] = True
prev[j + 1] = i # remember chain link
if not dp[n]:
return []
parts = deque()
at = n
while at > 0:
start = prev[at]
parts.appendleft(s[start:at])
at = start
return list(parts)vector<string> wordBreakPath(const string& s,
vector<string>& dict) {
TrieNode root;
for (auto& w : dict) root.insert(w);
int n = s.size();
vector<bool> dp(n + 1, false);
vector<int> prev(n + 1, -1); // where segment started
dp[0] = true;
prev[0] = 0;
for (int i = 0; i < n; i++) {
if (!dp[i]) continue;
TrieNode* cur = &root;
for (int j = i; j < n; j++) {
cur = cur->children[s[j] - 'a'];
if (!cur) break;
if (cur->isEnd && !dp[j + 1]) {
dp[j + 1] = true;
prev[j + 1] = i; // remember chain link
}
}
}
if (!dp[n]) return {};
deque<string> parts;
for (int at = n; at > 0; ) {
int start = prev[at];
parts.push_front(s.substr(start, at - start));
at = start;
}
return {parts.begin(), parts.end()};
}function wordBreakPath(s, wordDict) {
const root = {};
const END = "$";
for (const w of wordDict) {
let cur = root;
for (const ch of w) cur = cur[ch] ??= {};
cur[END] = true;
}
const n = s.length;
const dp = new Array(n + 1).fill(false);
const prev = new Array(n + 1).fill(-1);
dp[0] = true;
prev[0] = 0;
for (let i = 0; i < n; i++) {
if (!dp[i]) continue;
let cur = root;
for (let j = i; j < n; j++) {
cur = cur[s[j]];
if (!cur) break;
if (cur[END] && !dp[j + 1]) {
dp[j + 1] = true;
prev[j + 1] = i; // remember chain link
}
}
}
if (!dp[n]) return [];
const parts = [];
for (let at = n; at > 0; ) {
const start = prev[at];
parts.unshift(s.slice(start, at));
at = start;
}
return parts;
}
prev[]records which true cell spawned each true cell — follow it backwards fromdp[n].
Common Mistakes
Checking s.substring(i, j) against a hash set inside O(n²).
Works but re-hashes every substring — the trie walk shares prefix work and breaks early on dead ends.
Forgetting dp[i] must be true before walking.
Without it you’d allow segments floating in the middle with nothing before them.
Not marking visited when collecting ALL segmentations.
Memoize per position or you’ll enumerate exponentially many duplicate chains.
Complexity
| Metric | Value |
|---|---|
| Build trie | O(total dict chars) |
| DP | O(n · maxWordLen) — inner loop dies at first missing child |
| Space | O(dict chars + n) |
Premium Content
Unlock Word Break with Trie and all premium lessons with a subscription.
From ₹199.99/year — See plans