单词拆分 II

难度: Hard

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 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"]
输出:[]

提示：

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

Submission

运行时间: 18 ms

内存: 15.9 MB

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
         res = []
         def back_track(s, path,res):
                if(not s):
                    res.append(path[1:])
                for i in range(1,len(s)+1):
                    if(s[:i] in wordDict):
                        back_track(s[i:], path + " " + s[:i],res)
         back_track(s, "", res)
         return res

Explain

这个题解采用了回溯算法的思路。首先定义了一个回溯函数 back_track，它接受三个参数：当前待处理的字符串 s，当前已构建的句子 path，以及存储结果的列表 res。在回溯函数中，首先判断如果 s 为空，说明已经找到一个合法的句子，将 path 加入结果列表 res 中。然后遍历 s 的所有前缀，如果某个前缀出现在 wordDict 中，则继续递归调用回溯函数，处理剩余的字符串，并将当前前缀加入 path。最后在主函数中调用回溯函数，并返回结果列表 res。

时间复杂度: O(2^n * nw)

空间复杂度: O(2^n * n/w)

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
         res = []
         def back_track(s, path, res):
                # 如果 s 为空，说明找到一个合法的句子，将 path 加入结果列表
                if(not s):
                    res.append(path[1:])
                # 遍历 s 的所有前缀
                for i in range(1, len(s)+1):
                    # 如果前缀在 wordDict 中
                    if(s[:i] in wordDict):
                        # 继续递归调用，处理剩余字符串，并将当前前缀加入 path
                        back_track(s[i:], path + " " + s[:i], res)
         back_track(s, "", res)
         return res
```

Explore

在这个特定的回溯算法中，通过每次使用不同的剩余字符串s[i:]调用back_track函数来确保构建的句子是基于剩余单词的新组合。只有当整个输入字符串s被完全使用完，并且组合的单词顺序和边界与之前任何一次添加到res中的句子都不同时，才会将新的句子添加到res中。因此，算法设计本身通过路径和剩余字符串的管理避免了重复句子的生成。

回溯算法适用于这个问题因为它能够探索所有可能的单词组合，并且在找到有效解时可以即时回溯到上一个决策点。这种问题需要生成所有可能的句子组合，而不仅仅是判断是否可以拆分，这使得回溯算法成为一个理想选择。动态规划虽然可以用来判断字符串是否可以根据字典被有效拆分，但在生成所有可能组合的具体场景中，其实现会比回溯更复杂，效率可能也不如直接使用回溯算法。

在这个回溯算法中，对wordDict中的单词重复使用没有限制。每次递归调用back_track时，都从当前剩余的字符串s的前缀开始检查，只要前缀与字典中的某个单词匹配，就可以再次使用该单词。这意味着即使是同一个单词，只要它在输入字符串s中多次出现，就可以被重复利用来构成不同的句子组合。