0140. 单词拆分 II

题目地址（140. 单词拆分 II）

https://leetcode-cn.com/problems/word-break-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"]
输出:
[]

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

前置知识

• 回溯

• 笛卡尔积

公司

• 暂无

暴力回溯

思路

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

代码

代码支持：Python3, CPP

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

CPP Code:

class Solution {
    int maxLen = 0;
    unordered_set<string> ws;
    vector<int> m;
    vector<string> ans;
    bool dfs(string &s, int i, string tmp) {
        if (i == s.size()) {
            ans.push_back(tmp);
            return true;
        }
        if (m[i] == 0) return m[i];
        m[i] = 0;
        for (int j = min((int)s.size(), i + maxLen); j > i; --j) {
            auto sub = s.substr(i, j - i);
            if (ws.count(sub) && dfs(s, j, tmp.size() ? tmp + " " + sub : sub)) m[i] = 1;
        }
        return m[i];
    }
public:
    vector<string> wordBreak(string s, vector<string>& dict) {
        ws = { dict.begin(), dict.end() };
        for (auto &w : dict) maxLen = max(maxLen, (int)w.size());
        m.assign(s.size(), -1); // -1 = unvisited, 0 = can not reach end, 1 = can reach end.
        dfs(s, 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,

}

1. 当我们 DFS 探到底部的时候，也就是触及到 hi。我们就知道了，s[-2:] 可能组成的所有可能就是 ['hi', 'h', 'i']

2. 当我们 DFS 探到 worldhi 的时候。我们就知道了，s[-7:] 可能组成的所有可能就是 ['worldhi', 'worldh', 'worldi']

3. 如上只是一个分支的情况，如果有多个分支，那么步骤 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)

复杂度分析

令 C 为字典的总长度， N 为字典中最长的单词的长度。

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

• 空间复杂度：$O(C)$

这种记忆化递归的方式和 DP 思想一模一样， 大家可以将其改造为 DP，这个留给大家来完成。

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。