140. Word Break II

HardTrieMemoizationArrayHash TableStringDynamic ProgrammingBacktracking

Problem Description

You are given a string s and a dictionary of strings wordDict. Your task is to add spaces to the string s to break it into a sequence of valid dictionary words, creating complete sentences. You need to return all possible valid sentences that can be formed.

Key requirements:

Each word in the resulting sentence must exist in wordDict
The same word from the dictionary can be used multiple times in different positions
Return all possible valid segmentations of the string
The sentences can be returned in any order

For example, if s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], you could form:

"cats and dog"
"cat sand dog"

The solution uses a Trie data structure to efficiently store and search the dictionary words, combined with a depth-first search (DFS) approach to explore all possible word segmentations. The algorithm:

Builds a Trie from all words in wordDict for efficient prefix matching
Uses DFS to recursively try breaking the string at different positions
For each position i from 1 to the length of remaining string:
- Checks if s[:i] forms a valid word using the Trie
- If valid, recursively processes the remaining substring s[i:]
- Combines the current word with all valid segmentations of the remaining string
Returns all valid combinations joined with spaces

The base case occurs when the string is empty, returning an empty list within a list [[]] to properly combine with previous words in the recursion chain.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

No: While we could model this as a graph problem where each valid word forms an edge, the problem is fundamentally about string segmentation and finding all possible ways to break a string, not about traversing nodes and edges.

Need to solve for kth smallest/largest?

No: We need to find all possible valid sentences, not the kth smallest or largest element.

Involves Linked Lists?

No: The problem involves strings and arrays, not linked list data structures.

Does the problem have small constraints?

Yes: The problem typically has manageable constraints since we need to find all possible segmentations. The string length is usually limited (often ≤ 20-30 characters) because the number of possible segmentations can grow exponentially.

Brute force / Backtracking?

Yes: We need to explore all possible ways to break the string into valid words. At each position, we make a choice (where to break the string), explore that path recursively, and backtrack to try other possibilities. This is a classic backtracking pattern where we:
1. Try each possible word starting from the current position
2. If valid, recursively process the remaining string
3. Collect all valid combinations
4. Backtrack to try other word breaks

Conclusion: The flowchart correctly leads us to use a Backtracking approach for Word Break II, as we need to systematically explore all possible ways to segment the string into dictionary words.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When we need to find all possible ways to break a string into valid words, we face a decision-making problem at each position: "Where should I make the next cut?"

Think of it like cutting a piece of rope into segments where each segment must match one of the given patterns. At any point in the string, we have multiple choices - we could cut after 1 character, 2 characters, 3 characters, and so on. Each choice leads to a different remaining substring that needs to be processed.

This naturally suggests a recursive approach: try every possible first word, and for each valid first word, recursively solve the remaining substring. For example, with "catsanddog":

If we take "cat" as the first word, we need to solve "sanddog"
If we take "cats" as the first word, we need to solve "anddog"

The key insight is that we need to explore ALL valid paths, not just find one solution. This is where backtracking shines - it systematically explores every possibility and collects all valid solutions.

To optimize the word lookup process, we use a Trie data structure. Why? Because as we try different word lengths from a position (checking if s[0:1], s[0:2], s[0:3]... are valid words), a Trie allows us to efficiently check if a prefix exists and if it forms a complete word. This is more efficient than checking each substring against a list or even a hash set when we have many dictionary words.

The recursive structure becomes clear:

Base case: Empty string means we've successfully segmented the entire string
Recursive case: For each valid word starting at the current position, combine it with all valid segmentations of the remaining string
The result is naturally built by combining the current word choice with all possible completions

This backtracking approach guarantees we find all valid segmentations by systematically exploring every valid word break possibility.

Solution Implementation

1class Trie: 2 """Trie (prefix tree) data structure for efficient word lookups""" 3 4 def __init__(self): 5 # Array to store 26 children nodes (one for each lowercase letter) 6 self.children = [None] * 26 7 # Flag to mark if current node represents end of a word 8 self.is_end = False 9 10 def insert(self, word: str) -> None: 11 """Insert a word into the trie""" 12 node = self 13 for char in word: 14 # Calculate index for current character (0-25) 15 index = ord(char) - ord('a') 16 # Create new node if path doesn't exist 17 if node.children[index] is None: 18 node.children[index] = Trie() 19 # Move to next node 20 node = node.children[index] 21 # Mark the last node as end of word 22 node.is_end = True 23 24 def search(self, word: str) -> bool: 25 """Search for a complete word in the trie""" 26 node = self 27 for char in word: 28 # Calculate index for current character 29 index = ord(char) - ord('a') 30 # Return false if path doesn't exist 31 if node.children[index] is None: 32 return False 33 # Move to next node 34 node = node.children[index] 35 # Check if current node marks end of a valid word 36 return node.is_end 37 38 39class Solution: 40 def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: 41 """ 42 Break a string into words from dictionary and return all possible sentences. 43 44 Args: 45 s: Input string to break 46 wordDict: List of valid words 47 48 Returns: 49 List of all possible sentences formed by breaking the string 50 """ 51 52 def dfs(remaining_string: str) -> List[List[str]]: 53 """ 54 Recursively find all possible word combinations for the remaining string. 55 56 Args: 57 remaining_string: Substring yet to be processed 58 59 Returns: 60 List of word combinations, where each combination is a list of words 61 """ 62 # Base case: empty string returns empty combination 63 if not remaining_string: 64 return [[]] 65 66 result = [] 67 # Try all possible prefixes of the remaining string 68 for i in range(1, len(remaining_string) + 1): 69 prefix = remaining_string[:i] 70 # Check if prefix exists in dictionary 71 if trie.search(prefix): 72 # Recursively process the rest of the string 73 suffix_combinations = dfs(remaining_string[i:]) 74 # Add current prefix to all combinations from suffix 75 for combination in suffix_combinations: 76 result.append([prefix] + combination) 77 78 return result 79 80 # Build trie from dictionary words for efficient lookup 81 trie = Trie() 82 for word in wordDict: 83 trie.insert(word) 84 85 # Find all possible word combinations 86 all_combinations = dfs(s) 87 88 # Convert each combination list to a space-separated sentence 89 return [' '.join(combination) for combination in all_combinations] 90

1import java.util.*; 2import java.util.stream.Collectors; 3 4/** 5 * Trie (Prefix Tree) data structure for efficient word storage and retrieval 6 */ 7class Trie { 8 // Array to store 26 child nodes (for lowercase letters a-z) 9 private Trie[] children; 10 // Flag to mark if current node represents end of a word 11 private boolean isEndOfWord; 12 13 /** 14 * Constructor initializes the Trie node 15 */ 16 public Trie() { 17 this.children = new Trie[26]; 18 this.isEndOfWord = false; 19 } 20 21 /** 22 * Inserts a word into the Trie 23 * @param word The word to be inserted 24 */ 25 public void insert(String word) { 26 Trie currentNode = this; 27 28 // Traverse through each character in the word 29 for (char character : word.toCharArray()) { 30 // Convert character to index (0-25) 31 int index = character - 'a'; 32 33 // Create new node if path doesn't exist 34 if (currentNode.children[index] == null) { 35 currentNode.children[index] = new Trie(); 36 } 37 38 // Move to the child node 39 currentNode = currentNode.children[index]; 40 } 41 42 // Mark the end of the word 43 currentNode.isEndOfWord = true; 44 } 45 46 /** 47 * Searches for a complete word in the Trie 48 * @param word The word to search for 49 * @return true if the word exists in the Trie, false otherwise 50 */ 51 public boolean search(String word) { 52 Trie currentNode = this; 53 54 // Traverse through each character in the word 55 for (char character : word.toCharArray()) { 56 // Convert character to index (0-25) 57 int index = character - 'a'; 58 59 // Return false if path doesn't exist 60 if (currentNode.children[index] == null) { 61 return false; 62 } 63 64 // Move to the child node 65 currentNode = currentNode.children[index]; 66 } 67 68 // Check if current node marks the end of a word 69 return currentNode.isEndOfWord; 70 } 71} 72 73/** 74 * Solution class for Word Break II problem 75 * Given a string and a dictionary of words, returns all possible sentences 76 * that can be formed by breaking the string using dictionary words 77 */ 78class Solution { 79 private Trie trie; 80 81 /** 82 * Main method to break the string into valid sentences using dictionary words 83 * @param s The input string to break 84 * @param wordDict List of valid dictionary words 85 * @return List of all possible valid sentences 86 */ 87 public List<String> wordBreak(String s, List<String> wordDict) { 88 // Initialize Trie and insert all dictionary words 89 trie = new Trie(); 90 for (String word : wordDict) { 91 trie.insert(word); 92 } 93 94 // Get all possible word combinations using DFS 95 List<List<String>> wordCombinations = dfs(s); 96 97 // Convert list of word lists to list of sentences (space-separated) 98 return wordCombinations.stream() 99 .map(words -> String.join(" ", words)) 100 .collect(Collectors.toList()); 101 } 102 103 /** 104 * Recursive DFS helper method to find all valid word combinations 105 * @param remainingString The remaining substring to process 106 * @return List of all possible word combinations for the remaining string 107 */ 108 private List<List<String>> dfs(String remainingString) { 109 List<List<String>> result = new ArrayList<>(); 110 111 // Base case: empty string means we've successfully broken the entire string 112 if (remainingString.isEmpty()) { 113 result.add(new ArrayList<>()); 114 return result; 115 } 116 117 // Try all possible prefixes starting from index 1 118 for (int endIndex = 1; endIndex <= remainingString.length(); endIndex++) { 119 String prefix = remainingString.substring(0, endIndex); 120 121 // If prefix exists in dictionary, recursively process the remaining string 122 if (trie.search(prefix)) { 123 String suffix = remainingString.substring(endIndex); 124 List<List<String>> suffixCombinations = dfs(suffix); 125 126 // Add current prefix to each valid combination from suffix 127 for (List<String> combination : suffixCombinations) { 128 // Insert prefix at the beginning of the combination 129 combination.add(0, prefix); 130 result.add(combination); 131 } 132 } 133 } 134 135 return result; 136 } 137} 138

1#include <vector> 2#include <string> 3#include <unordered_set> 4#include <algorithm> 5 6using namespace std; 7 8/** 9 * Trie (Prefix Tree) data structure for efficient word storage and retrieval 10 */ 11class Trie { 12private: 13 // Array to store 26 child nodes (for lowercase letters a-z) 14 Trie* children[26]; 15 // Flag to mark if current node represents end of a word 16 bool isEndOfWord; 17 18public: 19 /** 20 * Constructor initializes the Trie node 21 */ 22 Trie() { 23 for (int i = 0; i < 26; i++) { 24 children[i] = nullptr; 25 } 26 isEndOfWord = false; 27 } 28 29 /** 30 * Destructor to free allocated memory 31 */ 32 ~Trie() { 33 for (int i = 0; i < 26; i++) { 34 if (children[i] != nullptr) { 35 delete children[i]; 36 } 37 } 38 } 39 40 /** 41 * Inserts a word into the Trie 42 * @param word The word to be inserted 43 */ 44 void insert(string word) { 45 Trie* currentNode = this; 46 47 // Traverse through each character in the word 48 for (char character : word) { 49 // Convert character to index (0-25) 50 int index = character - 'a'; 51 52 // Create new node if path doesn't exist 53 if (currentNode->children[index] == nullptr) { 54 currentNode->children[index] = new Trie(); 55 } 56 57 // Move to the child node 58 currentNode = currentNode->children[index]; 59 } 60 61 // Mark the end of the word 62 currentNode->isEndOfWord = true; 63 } 64 65 /** 66 * Searches for a complete word in the Trie 67 * @param word The word to search for 68 * @return true if the word exists in the Trie, false otherwise 69 */ 70 bool search(string word) { 71 Trie* currentNode = this; 72 73 // Traverse through each character in the word 74 for (char character : word) { 75 // Convert character to index (0-25) 76 int index = character - 'a'; 77 78 // Return false if path doesn't exist 79 if (currentNode->children[index] == nullptr) { 80 return false; 81 } 82 83 // Move to the child node 84 currentNode = currentNode->children[index]; 85 } 86 87 // Check if current node marks the end of a word 88 return currentNode->isEndOfWord; 89 } 90}; 91 92/** 93 * Solution class for Word Break II problem 94 * Given a string and a dictionary of words, returns all possible sentences 95 * that can be formed by breaking the string using dictionary words 96 */ 97class Solution { 98private: 99 Trie* trie; 100 101 /** 102 * Recursive DFS helper method to find all valid word combinations 103 * @param remainingString The remaining substring to process 104 * @return List of all possible word combinations for the remaining string 105 */ 106 vector<vector<string>> dfs(string remainingString) { 107 vector<vector<string>> result; 108 109 // Base case: empty string means we've successfully broken the entire string 110 if (remainingString.empty()) { 111 result.push_back(vector<string>()); 112 return result; 113 } 114 115 // Try all possible prefixes starting from index 1 116 for (int endIndex = 1; endIndex <= remainingString.length(); endIndex++) { 117 string prefix = remainingString.substr(0, endIndex); 118 119 // If prefix exists in dictionary, recursively process the remaining string 120 if (trie->search(prefix)) { 121 string suffix = remainingString.substr(endIndex); 122 vector<vector<string>> suffixCombinations = dfs(suffix); 123 124 // Add current prefix to each valid combination from suffix 125 for (vector<string>& combination : suffixCombinations) { 126 // Insert prefix at the beginning of the combination 127 combination.insert(combination.begin(), prefix); 128 result.push_back(combination); 129 } 130 } 131 } 132 133 return result; 134 } 135 136public: 137 /** 138 * Main method to break the string into valid sentences using dictionary words 139 * @param s The input string to break 140 * @param wordDict List of valid dictionary words 141 * @return List of all possible valid sentences 142 */ 143 vector<string> wordBreak(string s, vector<string>& wordDict) { 144 // Initialize Trie and insert all dictionary words 145 trie = new Trie(); 146 for (const string& word : wordDict) { 147 trie->insert(word); 148 } 149 150 // Get all possible word combinations using DFS 151 vector<vector<string>> wordCombinations = dfs(s); 152 153 // Convert list of word lists to list of sentences (space-separated) 154 vector<string> result; 155 for (const vector<string>& words : wordCombinations) { 156 string sentence = ""; 157 for (int i = 0; i < words.size(); i++) { 158 if (i > 0) { 159 sentence += " "; 160 } 161 sentence += words[i]; 162 } 163 result.push_back(sentence); 164 } 165 166 // Clean up allocated memory 167 delete trie; 168 169 return result; 170 } 171}; 172

1/** 2 * Trie (Prefix Tree) node structure for efficient word storage and retrieval 3 */ 4interface TrieNode { 5 // Map to store child nodes (for lowercase letters a-z) 6 children: Map<string, TrieNode>; 7 // Flag to mark if current node represents end of a word 8 isEndOfWord: boolean; 9} 10 11/** 12 * Creates a new Trie node 13 * @returns A new TrieNode with empty children and isEndOfWord set to false 14 */ 15function createTrieNode(): TrieNode { 16 return { 17 children: new Map<string, TrieNode>(), 18 isEndOfWord: false 19 }; 20} 21 22/** 23 * Global Trie root for storing dictionary words 24 */ 25let trieRoot: TrieNode; 26 27/** 28 * Inserts a word into the Trie 29 * @param word - The word to be inserted into the Trie 30 */ 31function insertIntoTrie(word: string): void { 32 let currentNode = trieRoot; 33 34 // Traverse through each character in the word 35 for (const character of word) { 36 // Create new node if path doesn't exist 37 if (!currentNode.children.has(character)) { 38 currentNode.children.set(character, createTrieNode()); 39 } 40 41 // Move to the child node 42 currentNode = currentNode.children.get(character)!; 43 } 44 45 // Mark the end of the word 46 currentNode.isEndOfWord = true; 47} 48 49/** 50 * Searches for a complete word in the Trie 51 * @param word - The word to search for in the Trie 52 * @returns true if the word exists in the Trie, false otherwise 53 */ 54function searchInTrie(word: string): boolean { 55 let currentNode = trieRoot; 56 57 // Traverse through each character in the word 58 for (const character of word) { 59 // Return false if path doesn't exist 60 if (!currentNode.children.has(character)) { 61 return false; 62 } 63 64 // Move to the child node 65 currentNode = currentNode.children.get(character)!; 66 } 67 68 // Check if current node marks the end of a word 69 return currentNode.isEndOfWord; 70} 71 72/** 73 * Main function to break the string into valid sentences using dictionary words 74 * @param s - The input string to break into words 75 * @param wordDict - Array of valid dictionary words 76 * @returns Array of all possible valid sentences (space-separated words) 77 */ 78function wordBreak(s: string, wordDict: string[]): string[] { 79 // Initialize Trie root and insert all dictionary words 80 trieRoot = createTrieNode(); 81 for (const word of wordDict) { 82 insertIntoTrie(word); 83 } 84 85 // Get all possible word combinations using DFS 86 const wordCombinations = dfsHelper(s); 87 88 // Convert array of word arrays to array of sentences (space-separated) 89 return wordCombinations.map(words => words.join(" ")); 90} 91 92/** 93 * Recursive DFS helper function to find all valid word combinations 94 * @param remainingString - The remaining substring to process 95 * @returns Array of all possible word combinations for the remaining string 96 */ 97function dfsHelper(remainingString: string): string[][] { 98 const result: string[][] = []; 99 100 // Base case: empty string means we've successfully broken the entire string 101 if (remainingString.length === 0) { 102 result.push([]); 103 return result; 104 } 105 106 // Try all possible prefixes starting from index 1 107 for (let endIndex = 1; endIndex <= remainingString.length; endIndex++) { 108 const prefix = remainingString.substring(0, endIndex); 109 110 // If prefix exists in dictionary, recursively process the remaining string 111 if (searchInTrie(prefix)) { 112 const suffix = remainingString.substring(endIndex); 113 const suffixCombinations = dfsHelper(suffix); 114 115 // Add current prefix to each valid combination from suffix 116 for (const combination of suffixCombinations) { 117 // Create new combination with prefix at the beginning 118 result.push([prefix, ...combination]); 119 } 120 } 121 } 122 123 return result; 124} 125

Solution Approach

The implementation uses a Trie data structure combined with depth-first search (DFS) backtracking to efficiently find all valid word segmentations.

Step 1: Build the Trie Structure

First, we create a Trie class to store all dictionary words:

Each node has 26 children (for lowercase letters a-z) stored as an array
is_end flag marks the end of a valid word
The insert method adds words character by character, creating nodes as needed
The search method checks if a given string exists as a complete word in the Trie

for w in wordDict:  trie.insert(w)

Step 2: Implement DFS Backtracking

The core algorithm is the dfs function that recursively explores all segmentations:

def dfs(s):  if not s:  return [[]] # Base case: empty string  res = []  for i in range(1, len(s) + 1):  if trie.search(s[:i]):  for v in dfs(s[i:]):  res.append([s[:i]] + v)  return res

The algorithm works as follows:

Base Case: When the string is empty, return [[]] - a list containing an empty list. This allows proper concatenation in the recursive calls.
Recursive Exploration: For each position i from 1 to the length of the string:
- Extract prefix s[:i] and check if it's a valid word using trie.search()
- If valid, recursively process the remaining substring s[i:]
- For each valid segmentation of the remaining string, prepend the current word
Building Results: Each recursive call returns a list of word lists. We combine the current word with each possible completion:
- If s[:i] is "cat" and dfs(s[i:]) returns [["sand", "dog"]]
- We create ["cat"] + ["sand", "dog"] = ["cat", "sand", "dog"]

Step 3: Format the Final Output

After getting all valid word combinations as lists of words, we join them with spaces:

ans = dfs(s) return [' '.join(v) for v in ans]

Time Complexity Analysis:

In the worst case, we might have O(2^n) possible segmentations (where every position could be a valid break point)
For each segmentation, we perform Trie searches which take O(m) where m is the word length
Overall: O(2^n * m) in the worst case

Space Complexity:

Trie storage: O(total characters in dictionary * 26)
Recursion stack: O(n) maximum depth
Result storage: O(2^n) for all possible segmentations

The combination of Trie for efficient word lookup and DFS for systematic exploration makes this solution both elegant and effective for finding all valid word break combinations.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with s = "catdog" and wordDict = ["cat", "dog", "ca", "t"].

Step 1: Build the Trie We insert all dictionary words into the Trie:

Insert "cat": c→a→t (mark t as end)
Insert "dog": d→o→g (mark g as end)
Insert "ca": c→a (mark a as end)
Insert "t": t (mark t as end)

Step 2: DFS Exploration from "catdog"

Starting with dfs("catdog"):

Try prefix of length 1: "c" - Not in Trie ✗
Try prefix of length 2: "ca" - Valid word! ✓
- Recursively call dfs("tdog")
  - Try "t" - Valid! ✓ → Call dfs("dog")
    - Try "d" - Not valid ✗
    - Try "do" - Not valid ✗
    - Try "dog" - Valid! ✓ → Call dfs("")
      - Base case returns [[]]
    - Returns [["dog"]]
  - Combine: "t" + ["dog"] = [["t", "dog"]]
  - Try "td", "tdo", "tdog" - All invalid ✗
  - Returns [["t", "dog"]]
- Combine: "ca" + ["t", "dog"] = [["ca", "t", "dog"]]
Try prefix of length 3: "cat" - Valid word! ✓
- Recursively call dfs("dog")
  - Try "d" - Not valid ✗
  - Try "do" - Not valid ✗
  - Try "dog" - Valid! ✓ → Call dfs("")
    - Base case returns [[]]
  - Returns [["dog"]]
- Combine: "cat" + ["dog"] = [["cat", "dog"]]
Try prefixes of length 4, 5, 6: "catd", "catdo", "catdog" - All invalid ✗

Step 3: Collect and Format Results

The DFS returns: [["ca", "t", "dog"], ["cat", "dog"]]

After joining with spaces:

["ca", "t", "dog"] → "ca t dog"
["cat", "dog"] → "cat dog"

Final Output: ["ca t dog", "cat dog"]

The key insight is how the recursion builds solutions bottom-up: the base case returns [[]], which allows each recursive level to properly append its word to form complete segmentations.

Time and Space Complexity

Time Complexity: O(n * 2^n)

The time complexity analysis breaks down as follows:

The DFS function explores all possible ways to break the string s into words from the dictionary
In the worst case, at each position i in the string, we can either start a new word or continue the current word, leading to 2^n possible segmentations where n is the length of string s
For each recursive call, we iterate through the string to find valid prefixes (up to n iterations)
The trie search operation takes O(m) time where m is the length of the word being searched, but since we're searching prefixes of s, this is bounded by O(n)
Building the final result requires joining the words, which in the worst case involves copying all 2^n valid segmentations
Therefore, the overall time complexity is O(n * 2^n)

Space Complexity: O(n * 2^n + m * k)

The space complexity consists of several components:

Trie storage: O(m * k) where m is the total number of characters across all words in wordDict and k is the size of the alphabet (26 for lowercase English letters)
Recursion stack: O(n) in the worst case when the recursion depth equals the length of the string
Result storage: In the worst case, we can have 2^n valid segmentations, and each segmentation contains words whose total length is n, resulting in O(n * 2^n) space for storing all results
The dominant term is O(n * 2^n) when considering large inputs where the exponential factor outweighs the trie storage
Therefore, the overall space complexity is O(n * 2^n + m * k)

Common Pitfalls

1. Exponential Time Complexity Without Memoization

The most significant pitfall in this solution is the lack of memoization, leading to redundant computations. When the same substring appears multiple times during recursion, we recalculate all its possible segmentations repeatedly.

Example Problem: Consider s = "aaaaaaa" with wordDict = ["a", "aa", "aaa"]. The substring "aaa" at the end might be reached through multiple paths:

"a" + "a" + "a" + "aaaa"
"aa" + "a" + "aaaa"
"a" + "aa" + "aaaa"
etc.

Each time we encounter "aaaa", we recalculate all its possible breaks, causing exponential time complexity.

Solution - Add Memoization:

class Solution:  def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:  def dfs(remaining_string: str) -> List[List[str]]:  # Check memo first  if remaining_string in memo:  return memo[remaining_string]   if not remaining_string:  return [[]]   result = []  for i in range(1, len(remaining_string) + 1):  prefix = remaining_string[:i]  if trie.search(prefix):  suffix_combinations = dfs(remaining_string[i:])  for combination in suffix_combinations:  result.append([prefix] + combination)   # Store result in memo before returning  memo[remaining_string] = result  return result   # Initialize memoization dictionary  memo = {}   trie = Trie()  for word in wordDict:  trie.insert(word)   all_combinations = dfs(s)  return [' '.join(combination) for combination in all_combinations]

2. Memory Issues with Large Result Sets

When there are many possible segmentations, storing all combinations in memory can cause memory overflow. For instance, a string with many overlapping valid words can generate an exponential number of valid sentences.

Solution - Use Generator for Memory Efficiency:

def dfs_generator(remaining_string: str):  """Yield combinations one at a time instead of storing all"""  if not remaining_string:  yield []  return   for i in range(1, len(remaining_string) + 1):  prefix = remaining_string[:i]  if trie.search(prefix):  for combination in dfs_generator(remaining_string[i:]):  yield [prefix] + combination

3. Inefficient String Slicing

Creating new string slices s[:i] and s[i:] at each recursive call creates many temporary string objects, impacting performance.

Solution - Use Indices Instead of String Slicing:

def dfs(start_index: int) -> List[List[str]]:  if start_index == len(s):  return [[]]   if start_index in memo:  return memo[start_index]   result = []  current_node = trie   for end_index in range(start_index, len(s)):  char = s[end_index]  index = ord(char) - ord('a')   if current_node.children[index] is None:  break # No more valid prefixes possible   current_node = current_node.children[index]   if current_node.is_end:  word = s[start_index:end_index + 1]  for combination in dfs(end_index + 1):  result.append([word] + combination)   memo[start_index] = result  return result

4. Not Pre-checking if Solution Exists

The algorithm might waste time exploring impossible cases. If certain characters in s don't appear in any dictionary word, we can fail fast.

Solution - Add Pre-validation:

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:  # Quick check: all characters in s must exist in some word  chars_in_dict = set(''.join(wordDict))  chars_in_s = set(s)   if not chars_in_s.issubset(chars_in_dict):  return [] # Impossible to break the string   # Continue with main algorithm...

These optimizations can significantly improve both time and space complexity, especially for strings with many possible segmentations or when dealing with large inputs.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don't know