# Word Break II
**Difficulty:** HARD
[External](https://leetcode.com/problems/word-break-ii)
Canonical: https://scaleengineer.com/dsa/problems/word-break-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Oracle](https://scaleengineer.com/companies/oracle), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Snap](https://scaleengineer.com/companies/snap), [X](https://scaleengineer.com/companies/x), [Grammarly](https://scaleengineer.com/companies/grammarly), [Moveworks](https://scaleengineer.com/companies/moveworks)
---
## Problem
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 105.

# Approaches
## Brute-Force Backtracking
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.
**Time:** O(n * 2^n) · **Space:** O(n^2 + |output|)
**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.
### Explanation
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.

```java
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        List<String> results = new ArrayList<>();
        backtrack(s, dict, 0, new StringBuilder(), results);
        return results;
    }

    private void backtrack(String s, Set<String> dict, int start, StringBuilder currentSentence, List<String> results) {
        if (start == s.length()) {
            results.add(currentSentence.toString().trim());
            return;
        }

        for (int end = start; end < s.length(); end++) {
            String word = s.substring(start, end + 1);
            if (dict.contains(word)) {
                int lenBefore = currentSentence.length();
                currentSentence.append(word).append(" ");
                backtrack(s, dict, end + 1, currentSentence, results);
                // Backtrack
                currentSentence.setLength(lenBefore);
            }
        }
    }
}
```
### 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.

## Dynamic Programming with Memoization
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.
**Time:** O(n^3 + |output|) · **Space:** O(n^2 + |output|)
**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.
### Explanation
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.

```java
class Solution {
    private Map<Integer, List<String>> memo;
    private Set<String> wordSet;
    private String s;

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.memo = new HashMap<>();
        this.wordSet = new HashSet<>(wordDict);
        this.s = s;
        return dfs(0);
    }

    private List<String> dfs(int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }

        List<String> results = new ArrayList<>();
        if (start == s.length()) {
            results.add("");
            return results;
        }

        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (wordSet.contains(word)) {
                List<String> sentencesFromSuffix = dfs(end);
                for (String suffix : sentencesFromSuffix) {
                    if (suffix.isEmpty()) {
                        results.add(word);
                    } else {
                        results.add(word + " " + suffix);
                    }
                }
            }
        }

        memo.put(start, results);
        return results;
    }
}
```
### 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)`.

# Solutions
### CSharp

```csharp
using 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 ; } }
```

### Java

```java
class 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 ; } }
```

### Python

```python
class 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
```