Word Break II

Statement

Given a string s and a dictionary of strings word_dict, add spaces to s to break it up into a sequence of valid words from word_dict. We are required to return all possible sequences of words (sentences). The order in which the sentences are listed is not significant.

Note: The same dictionary word may be reused multiple times in the segmentation.

Let’s say we have a string s = “catsanddog” and the word dictionary word_dict = [“cat”, “and”, “cats”, “dog”]. Of all the possible sentences that may be formed, consider the sentence “cats and dog”. These are the words in our sentence:

• “cats”
• “and”
• “dog”

and they are all present in the given dictionary.

We can break up s to form a different sentence, e.g., “cat sand dog”, but “sand” is not a word in our dictionary so we cannot consider this sentence as a valid sentence.

Constraints:

• $1 \leq$ s.length $\leq 60$

• $1 \leq$ word_dict.length $\leq 1000$

• $1 \leq$ word_dict[i].length $\leq 60$

• s as well as all the strings in word_dict consist only of lowercase English letters.

• All the strings in word_dict are unique.

Examples