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:

  • 11 \leq s.length 60\leq 60

  • 11 \leq word_dict.length 1000\leq 1000

  • 11 \leq word_dict[i].length 60\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

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.