Pattern Guide
Word Break & String Segmentation
"Can we split a string into valid words? DP with trie or set lookup."
Word break problems split a string into words from a dictionary. Variants: (1) can we split at all? (DP + set); (2) count ways to split; (3) return all valid splits (backtracking + memoization); (4) minimum cuts to make all parts valid; (5) decode ways (numeric strings). Core DP: dp[i] = can we split s[0..i-1] where dp[j] = true and s[j..i-1] is in dictionary.
Problems you can solve with this pattern
5 problems · click any to start solving
// Can we segment? O(n²) with set, O(n × maxWordLen) with trie
function canSegment(s, wordSet) {
const n = s.length;
const dp = new Array(n + 1).fill(false); dp[0] = true;
for (let i = 1; i <= n; i++)
for (let j = 0; j < i; j++)
if (dp[j] && wordSet.has(s.slice(j, i))) { dp[i] = true; break; }
return dp[n];
}
// Count ways to segment
function countSegments(s, wordSet) {
const n = s.length;
const dp = new Array(n + 1).fill(0); dp[0] = 1;
for (let i = 1; i <= n; i++)
for (let j = 0; j < i; j++)
if (dp[j] && wordSet.has(s.slice(j, i))) dp[i] += dp[j];
return dp[n];
}
// All valid segments (backtracking + memoization)
function allSegments(s, wordSet) {
const memo = new Map();
function dfs(start) {
if (memo.has(start)) return memo.get(start);
if (start === s.length) return [''];
const result = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (wordSet.has(word)) {
const rest = dfs(end);
for (const r of rest) result.push(r ? word + ' ' + r : word);
}
}
memo.set(start, result);
return result;
}
return dfs(0);
}Word break DP: dp[i] = true if s[0..i-1] can be segmented. Transition: dp[i] = true if ∃ j<i where dp[j]=true and s[j..i-1] is in the word set. O(n²) per lookup. Optimization: use a trie to match backward from position i — only check lengths that are valid word lengths. For count and all solutions: replace boolean dp with count/list.
// Can we segment? O(n²) with set, O(n × maxWordLen) with trie
function canSegment(s, wordSet) {
const n = s.length;
const dp = new Array(n + 1).fill(false); dp[0] = true;
for (let i = 1; i <= n; i++)
for (let j = 0; j < i; j++)
if (dp[j] && wordSet.has(s.slice(j, i))) { dp[i] = true; break; }
return dp[n];
}
// Count ways to segment
function countSegments(s, wordSet) {
const n = s.length;
const dp = new Array(n + 1).fill(0); dp[0] = 1;
for (let i = 1; i <= n; i++)
for (let j = 0; j < i; j++)
if (dp[j] && wordSet.has(s.slice(j, i))) dp[i] += dp[j];
return dp[n];
}
// All valid segments (backtracking + memoization)
function allSegments(s, wordSet) {
const memo = new Map();
function dfs(start) {
if (memo.has(start)) return memo.get(start);
if (start === s.length) return [''];
const result = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (wordSet.has(word)) {
const rest = dfs(end);
for (const r of rest) result.push(r ? word + ' ' + r : word);
}
}
memo.set(start, result);
return result;
}
return dfs(0);
}- Can segment: dp[i] = OR over valid splits ending at i
- Count ways: dp[i] = SUM over valid splits
- Min cost: dp[i] = MIN over valid splits + cost
- All solutions: backtracking + memoize by position
Optimization for large dictionaries:
- Trie lookup: match backward from position i, stop when no prefix exists
- Max word length: only check j in [i-maxLen, i)
Decode ways variants:
- Numeric: digits decode to 1-26
- With wildcard '*': count possible decodings
- With forbidden sequences: add extra DP states