题目描述
给定一个非空字符串 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"]
输出:
[]
算法
(动态规划 + 字符串哈希 + DFS) $O(n^2)$
和上一题类似,利用动态规划来判断是否能由wordDict中转移过来
状态表示:f[i]
表示是否能从wordDict中组成 为bool 值
状态转移方程: 如果s[i - k + 1 ... i]
在wordDict中出现过,则证明f[i]
可以从 f[i - k]
中转移过来
这里频繁的substr操作会带来额外的时间复杂度,所以可以用字符串哈希的方法来消除它;
这里由于要记录方案,我们新开一个哈希表记录每个状态可以由哪些状态转移来,最后dfs记录方案即可;
C++ 代码
typedef unsigned long long ULL;
class Solution {
public:
vector<ULL> hs, hw, p;
vector<bool> f;
unordered_map<int, vector<int>> trans;
vector<string> res;
public:
ULL get(int l, int r)
{
return hs[r] - hs[l - 1] * p[r - l + 1];
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
int n = s.size(), m = wordDict.size();
hs = vector<ULL>(n + 1, 0), hw = vector<ULL>(m + 1, 0), p = vector<ULL>(n + 1, 0);
f = vector<bool>(n + 1);
// 字符串哈希 初始化
p[0] = 1;
for(int i = 1; i <= n; i++)
{
hs[i] = hs[i - 1] * 131 + s[i - 1] - 'a' + 1;
p[i] = p[i - 1] * 131;
}
// 初始化 wordDict 的 哈希值
for(int i = 0; i < m; i++)
{
string sw = wordDict[i];
for(int j = 0; j < sw.size(); j++)
{
hw[i] = hw[i] * 131 + sw[j] - 'a' + 1;
}
}
// 状态转移
f[0] = true;
for(int i = 1; i <= n; i++)
for(int j = 0; j < m; j++)
{
int k = wordDict[j].size();
if(i >= k)
if(f[i - k] && get(i - k + 1, i) == hw[j])
{
f[i] = true;
trans[i].push_back(i - k);
}
}
if(!f[n]) return res;
else
{
vector<int> path;
dfs(n, path, s);
return res;
}
}
void dfs(int u, vector<int>& path, string& s)
{
if(u == 0)
{
stringstream ss;
for(int i = path.size() - 1; i; i--)
ss << s.substr(path[i], path[i - 1] - path[i]) << ' ';
ss << s.substr(path[0]);
res.push_back(ss.str());
}
else
{
for(auto x : trans[u])
{
path.push_back(x);
dfs(x, path, s);
path.pop_back();
}
}
}
};