DEBUG_INFO: title=Trie, type=object, isArray=, length=21
Word Break II
Given a string s and a string dictionary wordDict, return all possible sentences that can be formed by adding spaces to s such that each word is a valid dictionary word.
Visual Representation
s = "catsanddog", dict = ["cat","cats","and","sand","dog"]
Trie path 1: root -> c -> a -> t -> s (word) -> a -> n -> d (word) -> d -> o -> g (word)
Trie path 2: root -> c -> a -> t (word) -> s -> a -> n -> d (word) -> d -> o -> g (word)
Sentences:
1. "cats and dog"
2. "cat sand dog"
Hard Examples
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Java Python C++ JS Go
Approach 1
Level I: Standard Recursion Intuition
Iterate through the string s. If a prefix exists in the dictionary, recursively solve for the remaining suffix. O(2^N).
⏱ O(2^N) 💾 O(N)
import java . util . * ;
class Solution {
public List < String > wordBreak ( String s , List < String > wordDict ) {
return dfs ( s , wordDict , new HashMap < > ( ) ) ;
}
private List < String > dfs ( String s , List < String > wordDict , Map < String , List < String > > memo ) {
if ( memo . containsKey ( s ) ) return memo . get ( s ) ;
List < String > res = new ArrayList < > ( ) ;
if ( s . isEmpty ( ) ) {
res . add ( "" ) ;
return res ;
}
for ( String word : wordDict ) {
if ( s . startsWith ( word ) ) {
List < String > subList = dfs ( s . substring ( word . length ( ) ) , wordDict , memo ) ;
for ( String sub : subList ) {
res . add ( word + ( sub . isEmpty ( ) ? "" : " " ) + sub ) ;
}
}
}
memo . put ( s , res ) ;
return res ;
}
} Approach 2
Level III: Trie + DFS + Memoization Intuition
Use a Trie to store words for fast prefix lookups. Combine DFS with memoization to store results for each starting index.
⏱ O(N * 2^N) 💾 O(N * 2^N)
import java . util . * ;
class Solution {
class Node { Node [ ] children = new Node [ 26 ] ; String word = null ; }
public List < String > wordBreak ( String s , List < String > wordDict ) {
Node root = new Node ( ) ;
for ( String w : wordDict ) { Node c = root ; for ( char x : w . toCharArray ( ) ) { int i = x - 'a' ; if ( c . children [ i ] == null ) c . children [ i ] = new Node ( ) ; c = c . children [ i ] ; } c . word = w ; }
return dfs ( s , 0 , root , new HashMap < > ( ) ) ;
}
private List < String > dfs ( String s , int start , Node root , Map < Integer , List < String > > memo ) {
if ( memo . containsKey ( start ) ) return memo . get ( start ) ;
List < String > res = new ArrayList < > ( ) ;
if ( start == s . length ( ) ) { res . add ( "" ) ; return res ; }
Node curr = root ;
for ( int i = start ; i < s . length ( ) ; i ++ ) {
int idx = s . charAt ( i ) - 'a' ; if ( curr . children [ idx ] == null ) break ;
curr = curr . children [ idx ] ;
if ( curr . word != null ) {
List < String > sub = dfs ( s , i + 1 , root , memo ) ;
for ( String w : sub ) res . add ( curr . word + ( w . isEmpty ( ) ? "" : " " ) + w ) ;
}
}
memo . put ( start , res ) ; return res ;
}
}