Sentence Segmentation

You are given a non-empty string s and a dictionary of words. Your task is to insert spaces into s to construct all possible sentences where every word is a valid word from the dictionary. If no valid segmentation exists, output nothing.

For a given string s of length n and a dictionary wordDict, you need to find all possible ways to segment s into a space-separated sequence of one or more dictionary words.

The solution involves using recursion with memoization (or dynamic programming) to explore all potential breaks in the string. The final list of sentences should be printed in lexicographical order (i.e. sorted in ascending order).

For example, given s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], the valid sentences are:

• cat sand dog
• cats and dog

Note: When constructing your solution, if you refer to any mathematical expressions (for example, one could define the recurrence in terms of indices), please use LaTeX format. For instance, you might denote the recurrence as \[ \text{dp}[i] = \{ s[i:j] + " " + sub \mid s[i:j] \in \text{wordDict},\ sub \in \text{dp}[j] \} \]

inputFormat

The input is read from standard input (stdin) and has the following format:

Line 1: A non-empty string s. Line 2: An integer n representing the number of words in the dictionary. Next n lines: Each line contains a single word which is part of the dictionary.

outputFormat

Output all valid segmented sentences in lexicographical order, each on a new line to standard output (stdout). If there are no valid segmentations, output nothing.## sample

catsanddog
5
cat
cats
and
sand
dog

cat sand dog
cats and dog