Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: []
Constraints:
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s and wordDict[i] consist of only lowercase English letters.wordDict are unique.
The description was taken from https://leetcode.com/problems/word-break-ii/.
#O(N*2^N) Time, O(N*2^N) Space
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
output, words = [], {}
for word in wordDict:
words[word] = True
def backtrack(start:int, combo:list[str]) -> None:
if start == len(s):
output.append(" ".join(combo))
return
for i in range(start, len(s)):
word = s[start:i+1]
if word in words:
combo.append(word)
backtrack(i+1, combo)
combo.pop()
backtrack(0, [])
return outputIf a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
Here, we will traverse the string and if we find a substring that is in the words list that we were given, we will add that word to the current DFS path's combination and continue down that path. Once we have a combination that is the same size as the input string, we will have a valid combination so we will begin considering other paths.
Let's start by creating our output and a dictionary for the words we are given.
Then, we will push each word into it so that we can make these lookups in constant time.
output, words = [], {}
for word in wordDict:
words[word] = True
Next, we will create our recursive backtrack function.
The function will take a starting index that will act as a left bound for substrings to build, and a combination of words that we have added to the current DFS path.
def backtrack(start:int, combo:list[str]) -> None:
If our left bound starting index has reached the end of the input string, then we have placed all of the words that we need to into our combination within the current DFS path.
If that is the case, we will join the words together with spaces to form a sentence then append the sentence to the output.
if start == len(s):
output.append(" ".join(combo))
return
Otherwise, for each character of the input string between the starting index we were given in the current function call and the current index, we will take a slice of the string to form a word.
for i in range(start, len(s)):
word = s[start:i+1]
What would constitute a valid placement for this problem is if the word is in the words list.
If that is the case, we will append the word to the current combination, then travel down the DFS path with this word and increment our next left bound by one character after the current one.
if word in words:
combo.append(word)
backtrack(i+1, combo)
Once the DFS yoyo has returned to the current function call, we will pop the word we just appended to it so that we can append another word to this combination later.
This will allow us to generate each possible combination of words.
combo.pop()
Now that we have our backtrack function built, we just need to make the initial call by passing zero as the starting index and an empty combination.
Once our output is filled with each valid word sentence, we will return it.
backtrack(0, [])
return output