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.
1def wordBreak(s, wordDict):
2 def backtrack(start):
3 if start in memo:
4 return memo[start]
5 res = []
6 if start == len(s):
7 return ['']
8 for end in range(start + 1, len(s) + 1):
9 word = s[start:end]
10 if word in wordDict:
11 for sub_sentence in backtrack(end):
12 if sub_sentence:
13 res.append(word + ' ' + sub_sentence)
14 else:
15 res.append(word)
16 memo[start] = res
17 return res
18 memo = {}
19 return backtrack(0)
20
21# Example Usage
22s = "catsanddog"
23wordDict = {"cat", "cats", "and", "sand", "dog"}
24print(wordBreak(s, wordDict))The function wordBreak initiates the recursive backtrack function starting from index 0. The backtrack function attempts to form words by iterating over possible substrings. If a substring is found in the wordDict, it recursively attempts to formulate sentences with the rest of the string. Results of each position are stored in memo to avoid recalculations.
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
3
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.