Word break all segmentations
Your task
Given a string s and a dictionary of words, return all sentences (space-joined) where s can be segmented into a sequence of dictionary words. Words may be reused. Return the sentences sorted lexicographically. The length of s is at most 20 and the dictionary has at most 1000 words.
Examples
word_break_all(s: str, word_dict: list[str]) -> list[str]Example 1
Input
word_break_all("catsanddog", ["cat", "cats", "and", "sand", "dog"])Output
["cat sand dog", "cats and dog"]