140. Word Break II


Problem Description

This problem is about constructing sentences from a given string s without spaces, using a list of valid words provided in wordDict. We need to insert spaces into the original string s to create a sentence where every word is one that appears in the wordDict. Importantly, each word from the wordDict can be reused multiple times in constructing these sentences. The goal is to return all distinct sentences that can be formed by such segmentation in any order. The challenge lies in figuring out all valid combinations of words that fit together to remake the string s.

Intuition

To approach this problem, we can think of it as a classic backtracking problem, where we explore each possibility and backtrack if it doesn't lead to a valid solution. The primary strategy involves attempting to break the string s at every possible index and checking if the prefix up to that point is a word contained within the wordDict. If it is, we then recursively repeat this process on the remaining substring. By following this process, we eventually build up all valid sentences that can be constructed from the original string.

However, checking if a prefix is a valid word repeatedly could be inefficient, especially if wordDict is large. To optimize this, we can use a Trie, a tree-like data structure that is efficient for bulk searches like this one. We first insert all the dictionary words into the Trie, and then use it to quickly determine if a substring is a valid word as we perform the depth-first search (DFS).

We also use recursion with DFS to explore all possible sentence constructions. When we find a valid word, we work on the rest of the string, repeating the process until we reach the end of the string. By backtracking this way, we generate all possible sentences with valid dictionary words. Each path that leads us to the end of the string is a valid sentence, and we simply join the words to return them in the required format.

The time complexity of this approach can still be high due to the nature of the problem, as there might be an exponential number of possible sentences. However, using the Trie for efficient word lookups significantly reduces the search space we must explore compared to naively checking each substring against the wordDict.

Learn more about Trie, Memoization, Dynamic Programming and Backtracking patterns.

Solution Approach

The solution for this problem breaks down into several components, each with a clear purpose.

Firstly, let’s understand the [Trie](/problems/trie_intro) data structure implemented in the provided code. A Trie is a tree-like data structure that stores a dynamic set of strings, usually used for retrieval of keys in a dataset of strings. Here, each node represents a single character of a word and the path from the root to a specific node represents the prefix of words added so far.

  • The [Trie](/problems/trie_intro) class contains a method insert that takes a word and adds it to the Trie, character by character. It does this by iterating over each character in the word, calculating its index based on the ASCII value, and creating new Trie nodes as necessary.
  • The search method is used to determine if a specific word or prefix exists in the Trie. It traverses the Trie following the characters of the word and checking if the corresponding nodes exist; if it reaches the end of the word (is_end is True), the word is found.

With the help of the Trie for optimized searching, the Solution class encapsulates the core algorithm solving the problem:

  • A dfs (depth-first search) function is defined within the wordBreak method, which takes a substring of s as an argument. This function searches for all the ways that the substring can be split into words from wordDict.
  • If the input to the dfs function is an empty string, this indicates a valid sentence has been formed, hence it returns a list containing an empty list, representing the completion of a sentence.
  • For any given substring, the function iterates through its characters, using [trie](/problems/trie_intro).search to check if the current prefix is a valid dictionary word. If a valid word is found, it recursively calls dfs with the remaining substring.
  • Upon each successful return from dfs, res is updated with the combination of the found prefix and the result of subsequent recursive calls.

After setting up the [trie](/problems/trie_intro) with the given wordDict, the wordBreak method starts the depth-first search by calling dfs(s) with the entire original string s. The final result is constructed by joining each list of words (representing a valid sentence) in ans with spaces to form complete sentences.

In short, the solution uses recursion, backtracking, and the Trie data structure to efficiently explore all the potential ways of segmenting the string into words found in wordDict, without re-evaluating prefixes multiple times.

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

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following input:

  • s = "catsanddog"
  • wordDict = ["cat", "cats", "and", "sand", "dog"]

Using the provided solution approach, we perform these steps:

  1. We first insert all the words from the wordDict into the Trie.
  2. We then perform a depth-first search (DFS) on the string s, starting from the very beginning.
  3. At each step of the DFS, we check if the current prefix is a word in the Trie:
    • As we start, the first word we can form with the prefix of s is "cats". We find this by checking if "c", "ca", "cat", and finally "cats" are words in the wordDict through the Trie.
    • Having found "cats", we now consider the remainder of the string "anddog" and perform DFS on it.
  4. The next valid word we can find in "anddog" is "and". Similarly, after "and", we are left with "dog", which is also a valid word.
  5. We have now found one valid sentence, which is "cats and dog". This sentence is added to our final result list.
  6. Backtracking to the first step, instead of "cats", we could also choose "cat" as a valid prefix. So, we are left with "sanddog" to perform DFS on.
  7. In "sanddog", "sand" is a valid word, leaving us with "dog" which is, as previously found, a valid word.
  8. The second valid sentence formed is "cat sand dog", and this is also added to our final result.

By continuing this process until we can no longer find valid prefixes or the string is completely segmented into valid words, all possible sentences are found. Using the Trie, we ensure that we're not redundantly checking prefixes multiple times, which optimizes our search. The final result for this example would be a list of sentences: ["cats and dog", "cat sand dog"].

This example illustrates how the Trie data structure makes it efficient to look for valid words and how recursion with backtracking helps in exploring all possible sentence constructions.

Solution Implementation

1class Trie:
2    def __init__(self):
3        # Initialize a Trie node with children for each letter of the alphabet and a flag to mark the end of a word
4        self.children = [None] * 26
5        self.is_end_of_word = False
6
7    def insert(self, word):
8        # Insert a word into the Trie. Iterate through each character in the word, calculate its index, and create new Trie nodes as necessary.
9        node = self
10        for char in word:
11            index = ord(char) - ord('a')
12            if not node.children[index]:
13                node.children[index] = Trie()
14            node = node.children[index]
15        node.is_end_of_word = True
16
17    def search(self, word):
18        # Search for a word in the Trie. Traverse the Trie based on each character in the word. If we reach the end and the is_end_of_word flag is True, the word exists in the trie.
19        node = self
20        for char in word:
21            index = ord(char) - ord('a')
22            if not node.children[index]:
23                return False
24            node = node.children[index]
25        return node.is_end_of_word
26
27
28class Solution:
29    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
30        # Given a non-empty string s and a dictionary wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
31      
32        def dfs(substring):
33            # Depth-First Search function to build all possible sentences
34            if not substring:
35                # If there are no more characters left, we return an empty list within a list to signify a completed sentence.
36                return [[]]
37            results = []
38            # Check every possible prefix of the substring, if it is in the Trie (meaning it's a valid word), we recursively call dfs on the remaining substring.
39            for i in range(1, len(substring) + 1):
40                if trie.search(substring[:i]):
41                    for extension in dfs(substring[i:]):
42                        results.append([substring[:i]] + extension)
43            return results
44
45        # Initialize the Trie and insert each word from the dictionary into it.
46        trie = Trie()
47        for word in wordDict:
48            trie.insert(word)
49      
50        # Perform a DFS on the whole string and then join individual words with spaces to get all the sentences.
51        partial_sentences = dfs(s)
52        full_sentences = [' '.join(words) for words in partial_sentences]
53        return full_sentences
54
1import java.util.List;
2import java.util.ArrayList;
3import java.util.stream.Collectors;
4
5// Trie data structure for efficient word storage and retrieval
6class TrieNode {
7    // Array representing the children of each node
8    TrieNode[] children = new TrieNode[26];
9    // Flag to indicate the end of a word
10    boolean isEndOfWord;
11
12    // Method to insert a word into the trie
13    void insert(String word) {
14        TrieNode currentNode = this;
15        for (char ch : word.toCharArray()) {
16            int index = ch - 'a';
17            if (currentNode.children[index] == null) {
18                currentNode.children[index] = new TrieNode();
19            }
20            currentNode = currentNode.children[index];
21        }
22        currentNode.isEndOfWord = true;
23    }
24
25    // Method to search for a word in the trie
26    boolean search(String word) {
27        TrieNode currentNode = this;
28        for (char ch : word.toCharArray()) {
29            int index = ch - 'a';
30            if (currentNode.children[index] == null) {
31                return false;
32            }
33            currentNode = currentNode.children[index];
34        }
35        return currentNode.isEndOfWord;
36    }
37}
38
39public class Solution {
40    // Create a root trie node
41    private TrieNode rootTrieNode = new TrieNode();
42
43    // Main method to find all possible word breaks
44    public List<String> wordBreak(String s, List<String> wordDict) {
45        // Insert all words from the dictionary into the trie
46        for (String word : wordDict) {
47            rootTrieNode.insert(word);
48        }
49      
50        // Perform a depth-first search to find all combinations
51        List<List<String>> combinations = depthFirstSearch(s);
52        // Convert lists of strings into space-separated sentences
53        return combinations.stream()
54                           .map(words -> String.join(" ", words))
55                           .collect(Collectors.toList());
56    }
57
58    // Method for depth-first search to find word break combinations
59    private List<List<String>> depthFirstSearch(String s) {
60        List<List<String>> results = new ArrayList<>();
61        // If the string is empty, add an empty list (base case)
62        if ("".equals(s)) {
63            results.add(new ArrayList<>());
64            return results;
65        }
66
67        // Try breaking the string at different points to find valid words
68        for (int i = 1; i <= s.length(); ++i) {
69            // Check if the prefix is a valid word
70            if (rootTrieNode.search(s.substring(0, i))) {
71                // Recursively process the remaining string
72                for (List<String> suffixCombination : depthFirstSearch(s.substring(i))) {
73                    // Add the valid word to the beginning of the list
74                    suffixCombination.add(0, s.substring(0, i));
75                    // Add the new combination to the results
76                    results.add(suffixCombination);
77                }
78            }
79        }
80        return results;
81    }
82}
83
1#include <string>
2#include <vector>
3#include <unordered_set>
4#include <memory>
5#include <algorithm>
6
7// Trie data structure for efficient word storage and retrieval
8class TrieNode {
9public:
10    // Array representing the children of each node
11    std::vector<std::unique_ptr<TrieNode>> children;
12    // Flag to indicate the end of a word
13    bool isEndOfWord;
14
15    // Constructor initializes children for the size of the alphabet
16    TrieNode() : children(26), isEndOfWord(false) {}
17
18    // Method to insert a word into the trie
19    void insert(const std::string &word) {
20        TrieNode* currentNode = this;
21        for (char ch : word) {
22            int index = ch - 'a';
23            if (!currentNode->children[index]) {
24                currentNode->children[index] = std::make_unique<TrieNode>();
25            }
26            currentNode = currentNode->children[index].get();
27        }
28        currentNode->isEndOfWord = true;
29    }
30
31    // Method to search for a word in the trie
32    bool search(const std::string &word) {
33        TrieNode* currentNode = this;
34        for (char ch : word) {
35            int index = ch - 'a';
36            if (!(currentNode->children[index])) {
37                return false;
38            }
39            currentNode = currentNode->children[index].get();
40        }
41        return currentNode->isEndOfWord;
42    }
43};
44
45class Solution {
46private:
47    // Create a root trie node
48    TrieNode rootTrieNode;
49
50public:
51    // Main method to find all possible word breaks
52    std::vector<std::string> wordBreak(const std::string &s, const std::vector<std::string> &wordDict) {
53        // Insert all words from the dictionary into the trie
54        for (const std::string &word : wordDict) {
55            rootTrieNode.insert(word);
56        }
57
58        // Perform a depth-first search to find all combinations
59        std::vector<std::vector<std::string>> combinations = depthFirstSearch(s);
60        // Convert lists of strings into space-separated sentences
61        std::vector<std::string> result;
62        for (auto& words : combinations) {
63            result.push_back(join(words, " "));
64        }
65        return result;
66    }
67
68private:
69    // Method for depth-first search to find word break combinations
70    std::vector<std::vector<std::string>> depthFirstSearch(const std::string &s) {
71        std::vector<std::vector<std::string>> results;
72        // If the string is empty, add an empty list (base case)
73        if (s.empty()) {
74            results.emplace_back();
75            return results;
76        }
77
78        // Try breaking the string at different points to find valid words
79        for (int i = 1; i <= s.length(); ++i) {
80            // Check if the prefix is a valid word
81            if (rootTrieNode.search(s.substr(0, i))) {
82                // Recursively process the remaining string
83                for (auto suffixCombination : depthFirstSearch(s.substr(i))) {
84                    // Add the valid word to the beginning of the list
85                    suffixCombination.insert(suffixCombination.begin(), s.substr(0, i));
86                    // Add the new combination to the results
87                    results.push_back(suffixCombination);
88                }
89            }
90        }
91        return results;
92    }
93
94    // Helper function to concatenate vector of strings with a delimiter
95    std::string join(const std::vector<std::string> &words, const std::string &delimiter) {
96        std::string sentence;
97        for (int i = 0; i < words.size(); ++i) {
98            sentence += words[i];
99            if (i < words.size() - 1)
100                sentence += delimiter;
101        }
102        return sentence;
103    }
104};
105
1// Define the TrieNode structure for efficient word storage and retrieval
2interface TrieNode {
3    children: TrieNode[];
4    isEndOfWord: boolean;
5}
6
7// Function to create a new TrieNode
8const createTrieNode = (): TrieNode => {
9    return {
10        children: new Array<TrieNode>(26),
11        isEndOfWord: false
12    };
13};
14
15// Function to insert a word into the trie
16const insert = (root: TrieNode, word: string): void => {
17    let currentNode: TrieNode = root;
18    for (let ch of word) {
19        let index: number = ch.charCodeAt(0) - 'a'.charCodeAt(0);
20        if (!currentNode.children[index]) {
21            currentNode.children[index] = createTrieNode();
22        }
23        currentNode = currentNode.children[index];
24    }
25    currentNode.isEndOfWord = true;
26};
27
28// Function to search for a word in the trie
29const search = (root: TrieNode, word: string): boolean => {
30    let currentNode: TrieNode = root;
31    for (let ch of word) {
32        let index: number = ch.charCodeAt(0) - 'a'.charCodeAt(0);
33        if (!currentNode.children[index]) {
34            return false;
35        }
36        currentNode = currentNode.children[index];
37    }
38    return currentNode.isEndOfWord;
39};
40
41// Function to convert lists of strings into space-separated sentences
42const convertToStrings = (combinations: string[][]): string[] => {
43    return combinations.map(words => words.join(" "));
44};
45
46// Function for depth-first search to find word break combinations
47const depthFirstSearch = (root: TrieNode, s: string): string[][] => {
48    let results: string[][] = [];
49
50    // If the string is empty, add an empty list (base case)
51    if (s === "") {
52        results.push([]);
53        return results;
54    }
55
56    // Try breaking the string at different points to find valid words
57    for (let i = 1; i <= s.length; i++) {
58        // Check if the prefix is a valid word
59        if (search(root, s.substring(0, i))) {
60            // Recursively process the remaining string
61            let suffixCombinations: string[][] = depthFirstSearch(root, s.substring(i));
62            for (let suffixCombination of suffixCombinations) {
63                // Add the valid word to the beginning of the list
64                results.push([s.substring(0, i), ...suffixCombination]);
65            }
66        }
67    }
68    return results;
69};
70
71// Main function to find all possible word breaks
72const wordBreak = (s: string, wordDict: string[]): string[] => {
73    // Create a root trie node
74    let rootTrieNode: TrieNode = createTrieNode();
75
76    // Insert all words from the dictionary into the trie
77    for (let word of wordDict) {
78        insert(rootTrieNode, word);
79    }
80
81    // Perform a depth-first search to find all combinations
82    let combinations: string[][] = depthFirstSearch(rootTrieNode, s);
83
84    // Convert lists of strings into space-separated sentences
85    return convertToStrings(combinations);
86};
87
88// Example usage
89const s: string = "leetcode";
90const wordDict: string[] = ["leet", "code"];
91const sentences: string[] = wordBreak(s, wordDict);
92console.log(sentences); // Output: ["leet code"]
93

Time and Space Complexity

The given code implements a solution to the word break problem using a Trie and Depth First Search (DFS). It searches for all possible ways to segment a string into a list of words given a dictionary.

Time Complexity:

The time complexity of the function is determined mainly by the depth-first search algorithm dfs. For every substring s[:i] from the beginning of the string s up to i, the algorithm checks whether it is present in the trie. If the substring is present, it then recurses on the remaining substring s[i:].

Let n be the length of the input string s and k be the maximum length of a word in wordDict. In the worst case, the function dfs is called recursively for each prefix of the string s, which gives us O(n) calls in total. For each of these calls, the search in the trie takes O(k) time in the worst case.

However, due to the possibility of overlap among the substrings, without memoization, the number of total operations could be exponential in the worst case, leading to a time complexity of O(k * n^n) for the entire algorithm, as each position in the string might branch out up to n times in recursive calls, and this can happen for every other position in the string s.

Space Complexity:

The space complexity is determined by the size of the trie and the recursion stack.

  1. Trie Size: The trie could potentially contain all the prefixes of all the words in wordDict. In the worst case, if all words are of length k and all characters are distinct, the size would be O(m * k) where 'm' is the number of words in wordDict.

  2. Recursion Stack: The depth of the recursive stack will be at most n, the length of s, because the recursion could go as deep as the number of characters in s. When each function call returns a list of words, this list takes up space proportional to its length.

Adding these two parts together, the space complexity can be described as O(m * k + n). However, the actual space complexity also depends on the number of valid sentences that can be formed since all of them will eventually be stored in memory before they are concatenated and returned. This could, in certain cases, lead to a space complexity that is exponential to the length of s.

In summary, the time complexity is potentially O(k * n^n) due to the DFS without memoization, and the space complexity is O(m * k + n), not taking into account the extra space taken by the list of valid sentences, whose size can be very large depending on the input.

(Note: The time complexity can be significantly reduced by adding memoization to store intermediate results of dfs to avoid recalculating the same subproblems. Without memoization, time complexity can blow up exponentially with n, as discussed above.)

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄