"""
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
"""


from collections import deque

def wordBreak3(s, wordDict):
    size = len(s)
    assert size >0

    word_set = {word for word in wordDict}

    dp = [0]*(size+1)
    dp[0] = 1

    for i in range(1, size+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = 1
                break

    res = []
    if dp[-1]:
        queue = deque()
        _dfs(s, size, word_set, res, queue, dp)
    return res

def _dfs(s, length, word_set, res, path, dp):
    if length ==0:
        res.append(" ".join(path))
        return
    for i in range(length):
        if dp[i]:
            suffix = s[i:length]
            if suffix in word_set:
                path.appendleft(suffix)
                _dfs(s, i, word_set, res, path, dp)
                path.popleft()