Sponsored
Sponsored
This approach utilizes recursion to explore all possible partitions of the string, while memoization stores the results of subproblems to avoid redundant computations. We start from the first character, continuously check substrings against the dictionary, and recursively process the remaining parts of the string. The solutions for these parts are combined to form complete sentences. Memoization optimizes this by caching results of repeating subproblems.
Time Complexity: O(n^3), where n is the length of the input string, due to substring operations and memoization.
Space Complexity: O(n^3), for memoization of results and recursion stack.
1var wordBreak = function(s, wordDict) {
2 const memo = {};
3 function backtrack(start) {
4 if (start in memo) return memo[start];
5 const res = [];
6 if (start === s.length) return [''];
7 for (let end = start + 1; end <= s.length; end++) {
8 const word = s.substring(start, end);
9 if (wordDict.has(word)) {
10 const subsentences = backtrack(end);
11 for (const subsentence of subsentences) {
12 res.push(subsentence.length ? word + ' ' + subsentence : word);
13 }
14 }
15 }
16 memo[start] = res;
17 return res;
18 }
19 return backtrack(0);
20};
21
22// Example Usage
23const s = "catsanddog";
24const wordDict = new Set(["cat", "cats", "and", "sand", "dog"]);
25console.log(wordBreak(s, wordDict));The function wordBreak uses a closure backtrack to recursively find all valid sentences starting from each index of the string. For each starting index, it checks substrings against wordDict and attempts to form complete sentences using the rest of the string. Results are memoized to avoid recomputation.
This method uses dynamic programming to dynamically determine all possible sentences from the string based on the dictionary. We iterate through the string and for each suffix, if a word ends at the current position, all sentences that lead up to this word are combined with the word to form new valid sentences. A 2D list keeps track of sentences possible up to each character index.
Time Complexity: O(n^3), because of substring operations and iteration over previous results.
Space Complexity: O(n^3), for the storage of all potential sentences in a 2D list.
1import java.util.*;
2
The Java solution uses a list of lists dp where dp[i] holds all possible sentences that can be formed up to index i. By iterating over every substring, sentences are built incrementally and stored up to each index. Each word ending at index i is checked, and if valid, sentences are built by appending the word to sentences from the previous indexes.