Word Break Problem (Trie solution)
Problem Statement
Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Example:
Input: s = "leetcode", dictionary = ["leet", "code"]
Output: true
Explanation: "leetcode" can be split as "leet" + "code"
Input: s = "applepenapple", dictionary = ["apple", "pen"]
Output: true
Explanation: "apple" + "pen" + "apple"
Input: s = "catsandog", dictionary = ["cats", "dog", "sand", "and", "cat"]
Output: false
Noob-Friendly Explanation
Imagine you have a sentence with all the spaces removed: "ilikecats". You also have a dictionary with words like "i", "like", "cats", "cat", "sand". Your job is to figure out if you can split the sentence back into real words from the dictionary.
It's like playing with LEGO blocks — each dictionary word is a block, and you need to see if you can line up the blocks perfectly to build the entire string with no gaps and no leftovers.
We use a Trie to store the dictionary so we can quickly check "does any word start with these letters?" as we scan through the string.
Approach 1: Brute Force (Recursion)
Intuition
Try every possible split. At each position, check if the substring from the start to the current position is a valid dictionary word. If yes, recursively check the rest of the string.
Algorithm
- Start from index 0
- Try every possible end position from current index
- If substring is a dictionary word, recursively solve for the remaining string
- If we reach the end of the string, return true
import java.util.*;
class Solution {
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
return solve(s, wordSet, 0);
}
private static boolean solve(String s, Set<String> wordSet, int start) {
// If we've reached the end, string is fully segmented
if (start == s.length()) {
return true;
}
// Try every possible end position
for (int end = start + 1; end <= s.length(); end++) {
String substring = s.substring(start, end);
if (wordSet.contains(substring)) {
if (solve(s, wordSet, end)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
List<String> dict = Arrays.asList("leet", "code");
System.out.println(wordBreak("leetcode", dict)); // true
List<String> dict2 = Arrays.asList("cats", "dog", "sand", "and", "cat");
System.out.println(wordBreak("catsandog", dict2)); // false
}
}Complexity Analysis
- Time Complexity: O(2^N) — In the worst case, we try all possible partitions of the string
- Space Complexity: O(N) — Recursion stack depth
Approach 2: Optimal (Trie + Dynamic Programming)
Intuition
Build a Trie from the dictionary words. Use DP where dp[i] means "can we segment the string from index 0 to i-1?". For each position i, use the Trie to efficiently find all dictionary words starting at index i.
Algorithm
- Build a Trie from all dictionary words
- Create a boolean DP array of size n+1, with dp[0] = true (empty string)
- For each position i where dp[i] is true, traverse the Trie starting from character at index i
- Whenever we hit an end-of-word in the Trie at position j, set dp[j+1] = true
- Return dp[n]
import java.util.*;
class Solution {
static class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}
private static TrieNode root;
private static void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
public static boolean wordBreak(String s, List<String> wordDict) {
// Build Trie
root = new TrieNode();
for (String word : wordDict) {
insert(word);
}
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true; // empty string is always valid
for (int i = 0; i < n; i++) {
if (!dp[i]) continue; // skip if we can't reach this position
// Walk the Trie from position i
TrieNode current = root;
for (int j = i; j < n; j++) {
int index = s.charAt(j) - 'a';
if (current.children[index] == null) {
break; // no more words start with this prefix
}
current = current.children[index];
if (current.isEndOfWord) {
dp[j + 1] = true;
}
}
}
return dp[n];
}
public static void main(String[] args) {
List<String> dict = Arrays.asList("leet", "code");
System.out.println(wordBreak("leetcode", dict)); // true
List<String> dict2 = Arrays.asList("apple", "pen");
System.out.println(wordBreak("applepenapple", dict2)); // true
List<String> dict3 = Arrays.asList("cats", "dog", "sand", "and", "cat");
System.out.println(wordBreak("catsandog", dict3)); // false
}
}Complexity Analysis
- Time Complexity: O(N^2) — For each of the N positions, we may traverse up to N characters in the Trie
- Space Complexity: O(N + M * L) — DP array of size N, plus Trie storing M words of average length L
Key Takeaways
- Trie + DP = Power Combo: Trie speeds up dictionary lookups, DP avoids recomputation
- Why Trie over HashSet? For this problem, Trie lets us check all words starting at a position in one pass (no need to try each substring separately)
- dp[0] = true: The empty prefix is always "segmentable" — this is the base case
- Early Termination: If a character isn't in the Trie, we can stop early (no dictionary word continues from here)