LeetCode 140. 单词拆分 II

题目描述

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

微软有一道题和这个一样题目地址一样，感兴趣的可以看看完整面经。

难度：Middle

前置知识

回溯
笛卡尔积

公司

暂无

暴力回溯

思路

实际上这道题就是暴力回溯就好了，代码也比较简单。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ans = []
        n = len(s)

        def backtrack(temp, start):
            if start == n: ans.append(temp[1:])
            for i in range(start, n):
                if s[start:i + 1] in wordDict:
                    backtrack(temp + " " + s[start:i + 1], i + 1)
        backtrack('', 0)
        return ans

复杂度分析

时间复杂度：$O(2^N)$
空间复杂度：$O(2^N)$

笛卡尔积优化

思路

上面的代码会超时，测试用例会挂在如下：

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"[
  ("a",
  "aa",
  "aaa",
  "aaaa",
  "aaaaa",
  "aaaaaa",
  "aaaaaaa",
  "aaaaaaaa",
  "aaaaaaaaa",
  "aaaaaaaaaa")
];

也就是说 s 的长度是 151，这超时也就能够理解了，但是力扣的题目描述没有给数据范围。 如果是真实的面试，一定先问清楚数据范围。

接下来，我们考虑优化。

通过观察发现，对于一个字符串 s，比如 “helloworldhi” 而言，假设 dict 为：

{
  hi: true,
  h: true,
  i: true,
  world: true,
  hello: true,

}

当我们 DFS 探到底部的时候，也就是触及到 hi。我们就知道了，s[-2:] 可能组成的所有可能就是 [‘hi’, ‘h’, ‘i’]
当我们 DFS 探到 worldhi 的时候。我们就知道了，s[-7:] 可能组成的所有可能就是 [‘worldhi’, ‘worldh’, ‘worldi’]
如上只是一个分支的情况，如果有多个分支，那么步骤 1 就会被重复计算。

我们也不难看出，当我们 DFS 探到 worldhi 的时候，其可能的结果就是探测到的单词和上一步的所有可能的笛卡尔积。

因此一种优化思路就是将回溯的结果通过返回值的形式传递给父级函数，父级函数通过笛卡尔积构造 ans 即可。而这实际上和上面的解法复杂度是一样的，但是经过这样的改造，我们就可以使用记忆化技巧减少重复计算了。因此理论上，我们不存在回溯过程了。因此时间复杂度就是所有的组合，即一次遍历以及内部的笛卡尔积，也就是 $O(N ^ 2)$。

代码

代码支持：Python3

Python3 Code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        @lru_cache(None)
        def backtrack(start):
            ans = []
            if start == n:
                ans.append('')
            for i in range(start, n):
                if s[start:i + 1] in wordDict:
                    if start == 0: temp = s[start:i + 1]
                    else: temp = " " + s[start:i + 1]
                    ps = backtrack(i + 1)
                    for p in ps:
                        ans.append(temp + p)
            return ans
        return backtrack(0)

复杂度分析