1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/word-break-ii

2.解题方法

2.1.解题思路

记忆化搜索

2.2.解题步骤

第一步，构建记忆化搜索函数。递归任务：在s[:index]在wordDict的情况下，返回s[index:n]部分能够构建的合法切分数组

• 1.1.递归出口。s[n:n]为空字符，只有一种空组合

• 1.2.递归主体。枚举下一个切分j+1的位置，并进行递归，并将递归结果组合成结果数组

第二步，调用递归函数，返回结果

3.解题代码

python代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        # 思路：记忆化搜索
        n = len(s)
        wordDictSet = set(wordDict)
        # 第一步，构建记忆化搜索函数。递归任务：在s[:index]在wordDict的情况下，返回s[index:n]部分能够构建的合法切分数组
        @lru_cache
        def dfs(index):
            ans = []
            # 1.1.递归出口
            if index == n:
                return [[]]
            # 1.2.递归主体
            for j in range(index, n):
                word = s[index:j + 1]
                if word in wordDictSet:
                    ans1 = dfs(j + 1)
                    for a in ans1:
                        ans.append([word] + a)
            return ans
        ans = dfs(0)
        # print(ans)
        return [" ".join(arr) for arr in ans]

4.执行结果