# 180 - 140 单词拆分2

## 题目

给定一个非空字符串 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"] 输出: \[]

## 解答

学了回溯，看啥都像可以用回溯的样子

```python
from collections import deque

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        if len(s) == 0:
            return []
        word_set = {word for word in wordDict}
        dp = [0 for _ in range(len(s)+1)]
        dp[0] = 1
        for i in range(1, len(s)+1):
            for j in range(i):
                if dp[j]and s[j:i] in word_set:
                    dp[i] = 1
                    break
        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()
        if dp[-1]:
            queue = deque()
            dfs(s, len(s), word_set, res, queue, dp)
        return res
```

> Runtime: 44 ms, faster than 85.87% of Python3 online submissions for Word Break II.
>
> Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Word Break II.

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        from collections import defaultdict
        if len(s) == 0:
            return []
        cuts = [False]*(len(s)+1)
        cuts[0] = True
        segs = defaultdict(list)
        for i in range(1, len(s)+1):
            for j in range(i):
                rst = cuts[j]and (s[j:i]in wordDict)
                if rst is True:
                    cuts[i] = rst
                    segs[j].append(i)
        ret = []

        def backtrack(segs, start, path, ret):
            if start == len(s):
                ret.append(" ".join(path))
                return True
            else:
                for j in segs[start]:
                    path.append(s[start:j])
                    backtrack(segs, j, path, ret)
                    path.pop()
        if cuts[-1]is True:
            backtrack(segs, 0, [], ret)
        return ret
```

> Runtime: 112 ms, faster than 19.34% of Python3 online submissions for Word Break II.
>
> Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Word Break II.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joey-zhouyicheng.gitbook.io/leetcode/180-140-dan-ci-chai-fen-2.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.