MediumTrie

Word Break

Explanation & Solution

Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Use a trie combined with dynamic programming to solve this problem efficiently.

Input:s = "leetcode", wordDict = ["leet","code"]

leet

code

Output: true

Explanation: "leetcode" can be segmented as "leet code".

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters
All the strings of wordDict are unique

Approach

Trie pattern

1. Build a Trie from the Dictionary

Create a TrieNode class with children and an isEnd flag
Insert every word from wordDict into the trie character by character
Mark the last node of each word with isEnd = true

2. Initialize DP Array

Create a boolean array dp of size n + 1 (where n is the length of s)
dp[i] means the substring s[0..i-1] can be segmented into dictionary words
Set dp[0] = true (empty string is always valid)

3. Fill DP Using Trie Lookups

For each index i where dp[i] is true:
Start traversing the trie from the root, matching characters s[i], s[i+1], ...
If at any point the trie character is missing, break (no dictionary word starts this way)
If we reach a node with isEnd = true, set dp[j + 1] = true (we found a valid word from index i to j)
Continue matching to find longer dictionary words starting at i

4. Return Result

Return dp[n] which indicates whether the entire string s can be segmented

Key Insight

The trie allows us to check all dictionary words starting at position i in a single pass through the string, avoiding redundant prefix comparisons
Combined with DP, this achieves **O(n * L)** time complexity where L is the maximum word length in the dictionary
This is more efficient than checking each word individually, especially when the dictionary is large

Visualization

Input:

[l, e, e, t, c, o, d, e]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Palindrome Pairs

Longest Common Prefix