Word Break (trie solution)
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
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];}