Word Break (trie solution)

Medium

Problem

Same as Word Break — can s be split into dictionary words? — but store the dictionary in a trie, so that from each start index you walk forward only along real word prefixes.

Example 1

Input:  s = "ilikesamsung", dict = ["i", "like", "sam", "sung", "samsung"]
Output: true

Also asked as: Word Break Problem | (Trie solution)

Test cases

Case 1

Input:    "ilikesamsung", ["i","like","sam","sung","samsung"]
Expected: true

Case 2

Input:    "catsandog", ["cats","dog","sand","and","cat"]
Expected: false

Case 3

Input:    "aaaa", ["aa"]
Expected: true

Case 4

Input:    "a", ["b"]
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP over prefixes, dictionary stored in a trie

Time O(n² ) worst, faster in practiceSpace O(dict)

dp[i] = s[0..i) is breakable. From each true dp[j], walk the trie along s[j..] and set dp[k] wherever you hit a word end.

function wordBreakTrie(s, dict) {
const root = { children: new Map(), end: false };
for (const w of dict) {
let node = root;
for (const c of w) { if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false }); node = node.children.get(c); }
node.end = true;
}
const dp = Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 0; i < s.length; i++) {
if (!dp[i]) continue;
let node = root;
for (let j = i; j < s.length; j++) {
const c = s[j];
if (!node.children.has(c)) break;
node = node.children.get(c);
if (node.end) dp[j + 1] = true;
}
}
return dp[s.length];
}