140. 单词拆分 II

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

  • 分隔时可以重复使用字典中的单词。

  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
4
5
6
7
8
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：

1
2
3
4
5
6
7
8
9
10
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

1
2
3
4
5
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

思路

判断是否可分用动态规划，求具体解使用回溯。

与139. 单词拆分思想类似，139题可以使用动态规划的方法，或记忆化搜索。但是此题由于样例特殊，可能出现前半段很多解，后半段无解的情况，例如下面的测试用例会导致运行超时。

1
2
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
wordDict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

记忆化搜索 vs. 动态规划

  • 暴力搜索会产生很多重复的子问题，记忆化搜索记录搜索结果，再次进入相同的子问题直接返回结果（用空间去换时间，与动态规划类似）。
  • 记忆化搜索是自顶向下求解，动态规划是自底向上。本题中使用自顶向下的方法将不可拆分的情况自动剪枝，效率优于自底向上的动态规划。

代码

  • 为了加快判断字符串是否在单词列表中，使用哈希方法unordered_set加快查找。
  • ans[i]保存以i为开始下标的字符串s构成的单词拆分结果。
  • seen[i]表示以i为开始下标的字符串s是否被搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    vector<int> seen;
    vector<vector<string>> ans;
    unordered_set<string> _set;
    int n;
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        seen = vector<int>(n + 1);
        ans = vector<vector<string>>(n + 1, vector<string>());
        // 哈希set，快速查找
        _set = unordered_set(wordDict.begin(), wordDict.end());
        backtrack(s, 0);
        return ans[0];
    }
    void backtrack(const string& s, int index) {
        if(index >= n || seen[index]) return;
        seen[index] = 1;
        // substr(index, length)切割的单词区间为[index, index+length)
        // 要取等号，因为i=n时，全部匹配。
        for(int i = index + 1;i <= n;i++) {
            auto st = s.substr(index, i - index);
            // 找到了
            if(_set.find(st) != _set.end()) {
                if(i == n) {
                    ans[index].push_back(st);
                } else {
                    backtrack(s, i);
                    if(ans[i].size() != 0) {
                        for(auto sit:ans[i]) {
                            ans[index].push_back(st+" "+sit);
                        }
                    }   
                }
            }
        }
    }
};