Word Break II

Hard

#0140Time: O(n * 2^n)Space: O(n^2 + |output|)9 companies

Patterns

Dynamic Programming Backtracking Memoization

Data structures

Array Hash Table String Trie

Companies

Dropbox Oracle ServiceNow TikTok

Prompt

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Constraints:

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
Input is generated in a way that the length of the answer doesn't exceed 10⁵.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard backtracking algorithm to explore all possible ways to partition the string. It recursively tries to form a valid word starting from the current position. If a valid word is found, it makes a recursive call for the rest of the string. This process continues until the entire string is segmented or all possibilities are exhausted.

Algorithm

Create a Set from wordDict for efficient lookups.
Define a recursive function backtrack(s, dict, start, currentSentence, results).
Base Case: If start reaches the end of the string s, a valid sentence has been formed. Add the currentSentence (after trimming) to the results list and return.
Recursive Step: Iterate with an end index from start to the end of the string.
For each end, extract the substring word = s.substring(start, end + 1).
If word is found in the dictionary dict:
- Append word and a space to the currentSentence.
- Make a recursive call: backtrack(s, dict, end + 1, currentSentence, results).
- Backtrack: After the recursive call returns, undo the change to currentSentence to explore other possibilities from the same state.

Walkthrough

We define a helper function, backtrack(index, currentPath), which tries to find segmentations starting from index. The currentPath stores the sequence of words forming the sentence so far. The base case for the recursion is when index reaches the end of the string s. At this point, a valid segmentation has been found, so we join the words in currentPath with spaces and add it to our final result list. In the recursive step, we iterate from index to the end of the string. For each end index, we consider the substring s.substring(index, end + 1). If this substring exists in the wordDict, we add it to our currentPath and make a recursive call backtrack(end + 1, currentPath). After the recursive call returns, we must 'backtrack' by removing the word we just added from currentPath to explore other possibilities. This method explores the entire search space, but it's inefficient because it may solve the same subproblem (segmenting a particular suffix of s) multiple times.

1class Solution {2    public List<String> wordBreak(String s, List<String> wordDict) {3        Set<String> dict = new HashSet<>(wordDict);4        List<String> results = new ArrayList<>();5        backtrack(s, dict, 0, new StringBuilder(), results);6        return results;7    }8 9    private void backtrack(String s, Set<String> dict, int start, StringBuilder currentSentence, List<String> results) {10        if (start == s.length()) {11            results.add(currentSentence.toString().trim());12            return;13        }14 15        for (int end = start; end < s.length(); end++) {16            String word = s.substring(start, end + 1);17            if (dict.contains(word)) {18                int lenBefore = currentSentence.length();19                currentSentence.append(word).append(" ");20                backtrack(s, dict, end + 1, currentSentence, results);21                // Backtrack22                currentSentence.setLength(lenBefore);23            }24        }25    }26}

Complexity

Time

O(n * 2^n)

Space

O(n^2 + |output|)

Trade-offs

Pros

Conceptually simple and follows a direct, recursive logic.
It correctly finds all possible segmentations if given enough time.

Cons

Extremely inefficient due to the repeated computation of results for the same subproblems (i.e., segmenting the same suffix of the string multiple times).
Very likely to result in a 'Time Limit Exceeded' (TLE) error for non-trivial inputs.

This approach optimizes the brute-force backtracking by using memoization, a key technique in dynamic programming. It stores the results of subproblems to avoid redundant computations. Specifically, it remembers all possible ways to segment a particular suffix of the string once it has been computed, so it never has to compute it again.

Algorithm

Initialize a memoization map memo and a Set for the dictionary.
Define a recursive function dfs(start) that returns a list of all valid sentences for the suffix s.substring(start).
Memoization Check: If memo already contains the result for start, return the cached value memo.get(start).
Base Case: If start equals s.length(), it means the end of the string is reached. Return a list containing a single empty string "" to act as a signal for the calling function.
Recursive Step:
- Initialize an empty list currentResults.
- Loop with end from start + 1 to s.length().
- Extract word = s.substring(start, end).
- If word is in the dictionary:
  - Recursively call List<String> suffixSentences = dfs(end).
  - For each suffix in suffixSentences, form a new sentence by prepending word (and a space if suffix is not empty). Add this new sentence to currentResults.
Memoize and Return: Store currentResults in memo.put(start, currentResults) and return it.
The final answer is the result of the initial call dfs(0).

Walkthrough

The core idea is to create a function, say dfs(start), that returns a list of all possible valid sentences that can be formed from the suffix of the string s starting at start. We use a map, memo, to store the results, where memo.get(start) will be the cached list of sentences for the suffix s.substring(start). Before computing dfs(start), we check if the result is already in memo. If so, we return the cached value immediately. The base case is when start reaches the end of the string (s.length()). This signifies a successful segmentation, and we return a list containing a single empty string "". This empty string acts as a sentinel value that helps in constructing the sentences in the calling function. In the main logic, we iterate from end = start + 1 to s.length(). We check if the prefix word = s.substring(start, end) is in the dictionary. If it is, we recursively call dfs(end) to get all segmentations for the rest of the string. For each suffixSentence returned, we combine it with the current word (e.g., word + " " + suffixSentence) and add the new sentence to our list of results for the current start index. Finally, we store this list in memo and return it.

1class Solution {2    private Map<Integer, List<String>> memo;3    private Set<String> wordSet;4    private String s;5 6    public List<String> wordBreak(String s, List<String> wordDict) {7        this.memo = new HashMap<>();8        this.wordSet = new HashSet<>(wordDict);9        this.s = s;10        return dfs(0);11    }12 13    private List<String> dfs(int start) {14        if (memo.containsKey(start)) {15            return memo.get(start);16        }17 18        List<String> results = new ArrayList<>();19        if (start == s.length()) {20            results.add("");21            return results;22        }23 24        for (int end = start + 1; end <= s.length(); end++) {25            String word = s.substring(start, end);26            if (wordSet.contains(word)) {27                List<String> sentencesFromSuffix = dfs(end);28                for (String suffix : sentencesFromSuffix) {29                    if (suffix.isEmpty()) {30                        results.add(word);31                    } else {32                        results.add(word + " " + suffix);33                    }34                }35            }36        }37 38        memo.put(start, results);39        return results;40    }41}

Complexity

Time

O(n^3 + |output|)

Space

O(n^2 + |output|)

Trade-offs

Pros

Significantly more efficient than brute-force as it avoids recomputing solutions for subproblems.
Effectively handles overlapping subproblems, which is the main source of inefficiency in the brute-force method.
Guaranteed to pass within typical time limits for the given constraints.

Cons

Requires extra space for the memoization table, which can be significant if the string is long.
The implementation is slightly more complex than the brute-force approach due to the memoization logic.

Solutions

Solution

1using System ; using System.Collections.Generic ; using System.Linq ; using System.Text ; class Node { public int Index1 { get ; set ; } public int Index2 { get ; set ; } } public class Solution { public IList < string > WordBreak ( string s , IList < string > wordDict ) { var paths = new List < Tuple < int , string >>[ s . Length + 1 ]; paths [ s . Length ] = new List < Tuple < int , string >> { Tuple . Create (- 1 , ( string ) null ) }; var wordDictGroup = wordDict . GroupBy ( word => word . Length ); for ( var i = s . Length - 1 ; i >= 0 ; -- i ) { paths [ i ] = new List < Tuple < int , string >>(); foreach ( var wordGroup in wordDictGroup ) { var wordLength = wordGroup . Key ; if ( i + wordLength <= s . Length && paths [ i + wordLength ]. Count > 0 ) { foreach ( var word in wordGroup ) { if ( s . Substring ( i , wordLength ) == word ) { paths [ i ]. Add ( Tuple . Create ( i + wordLength , word )); } } } } } return GenerateResults ( paths ); } private IList < string > GenerateResults ( List < Tuple < int , string >>[] paths ) { var results = new List < string >(); var sb = new StringBuilder (); var stack = new Stack < Node >(); stack . Push ( new Node ()); while ( stack . Count > 0 ) { var node = stack . Peek (); if ( node . Index1 == paths . Length - 1 || node . Index2 == paths [ node . Index1 ]. Count ) { if ( node . Index1 == paths . Length - 1 ) { results . Add ( sb . ToString ()); } stack . Pop (); if ( stack . Count > 0 ) { var parent = stack . Peek (); var length = paths [ parent . Index1 ][ parent . Index2 - 1 ]. Item2 . Length ; if ( length < sb . Length ) ++ length ; sb . Remove ( sb . Length - length , length ); } } else { var newNode = new Node { Index1 = paths [ node . Index1 ][ node . Index2 ]. Item1 , Index2 = 0 }; if ( sb . Length != 0 ) { sb . Append ( ' ' ); } sb . Append ( paths [ node . Index1 ][ node . Index2 ]. Item2 ); stack . Push ( newNode ); ++ node . Index2 ; } } return results ; } }

1class Trie { Trie [] children = new Trie [ 26 ]; boolean isEnd ; void insert ( String word ) { Trie node = this ; for ( char c : word . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; } node . isEnd = true ; } boolean search ( String word ) { Trie node = this ; for ( char c : word . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { return false ; } node = node . children [ c ]; } return node . isEnd ; } } class Solution { private Trie trie = new Trie (); public List < String > wordBreak ( String s , List < String > wordDict ) { for ( String w : wordDict ) { trie . insert ( w ); } List < List < String >> res = dfs ( s ); return res . stream (). map ( e -> String . join ( " " , e )). collect ( Collectors . toList ()); } private List < List < String >> dfs ( String s ) { List < List < String >> res = new ArrayList <>(); if ( "" . equals ( s )) { res . add ( new ArrayList <>()); return res ; } for ( int i = 1 ; i <= s . length (); ++ i ) { if ( trie . search ( s . substring ( 0 , i ))) { for ( List < String > v : dfs ( s . substring ( i ))) { v . add ( 0 , s . substring ( 0 , i )); res . add ( v ); } } } return res ; } }

1class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False def insert ( self , word ): node = self for c in word : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True def search ( self , word ): node = self for c in word : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return False node = node . children [ idx ] return node . is_end class Solution : def wordBreak ( self , s : str , wordDict : List [ str ]) -> List [ str ]: def dfs ( s ): if not s : return [[]] # list of list res = [] for i in range ( 1 , len ( s ) + 1 ): # starts from 1, i is excluded in s[:i] if trie . search ( s [: i ]): # if below dfs() returns empty, then returned res also empty for v in dfs ( s [ i :]): res . append ([ s [: i ]] + v ) # [1] + [2,3] ==> [1, 2, 3] return res trie = Trie () for w in wordDict : trie . insert ( w ) ans = dfs ( s ) return [ ' ' . join ( v ) for v in ans ] ############# class Solution : def wordBreak ( self , s , wordDict ): """ :type s: str :type wordDict: Set[str] :rtype: List[str] """ res = [] if not self . check_word_break ( s , wordDict ): return res queue = [( 0 , "" )] slen = len ( s ) len_list = set ( len ( w ) for w in wordDict ) while queue : tmp_queue = [] for q in queue : start , path = q for l in len_list : if start + l <= slen and s [ start : start + l ] in wordDict : new_node = ( start + l , path + " " + s [ start : start + l ] if path else s [ start : start + l ]) tmp_queue . append ( new_node ) if start + l == slen : res . append ( new_node [ 1 ]) queue = tmp_queue return res def check_word_break ( self , s , wordDict ): """ :type s: str :type wordDict: Set[str] :rtype: bool """ queue = [ 0 ] slen = len ( s ) len_list = set ( len ( w ) for w in wordDict ) visited = [ 0 for _ in range ( slen + 1 )] while queue : tmp_queue = [] for start in queue : for l in len_list : if s [ start : start + l ] in wordDict : if start + l == slen : return True if not visited [ start + l ]: tmp_queue . append ( start + l ) visited [ start + l ] = 1 queue = tmp_queue

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem