Facebook Pixel

140. Word Break II

HardTrieMemoizationArrayHash TableStringDynamic ProgrammingBacktracking
Leetcode Link

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:

  1. Builds a Trie from all words in wordDict for efficient prefix matching
  2. Uses DFS to recursively try breaking the string at different positions
  3. 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
  4. 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:

  1. Base case: Empty string means we've successfully segmented the entire string
  2. Recursive case: For each valid word starting at the current position, combine it with all valid segmentations of the remaining string
  3. 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 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:

  1. Base Case: When the string is empty, return [[]] - a list containing an empty list. This allows proper concatenation in the recursive calls.

  2. 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

  3. 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 3-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.

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

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 3-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More