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.
Which data structure is used in a depth first search?
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 methodinsertthat 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
searchmethod 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_endisTrue), 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 thewordBreakmethod, which takes a substring ofsas an argument. This function searches for all the ways that the substring can be split into words fromwordDict. - If the input to the
dfsfunction 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).searchto check if the current prefix is a valid dictionary word. If a valid word is found, it recursively callsdfswith the remaining substring. - Upon each successful return from
dfs,resis 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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Example 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:
- We first insert all the words from the
wordDictinto the Trie. - We then perform a depth-first search (DFS) on the string
s, starting from the very beginning. - 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
sis "cats". We find this by checking if "c", "ca", "cat", and finally "cats" are words in thewordDictthrough the Trie. - Having found "cats", we now consider the remainder of the string "anddog" and perform DFS on it.
- As we start, the first word we can form with the prefix of
- 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.
- We have now found one valid sentence, which is "cats and dog". This sentence is added to our final result list.
- 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.
- In "sanddog", "sand" is a valid word, leaving us with "dog" which is, as previously found, a valid word.
- 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
541import 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}
831#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};
1051// 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"]
93Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Time 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.
-
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 lengthkand all characters are distinct, the size would be O(m * k) where 'm' is the number of words inwordDict. -
Recursion Stack: The depth of the recursive stack will be at most
n, the length ofs, because the recursion could go as deep as the number of characters ins. 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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
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 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
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
Got a question? Ask the Teaching 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.