0472. Concatenated Words
========================
题目信息
--------
:题号: 0472
:难度: Hard
:主题: 单词数组、字符串拼接、较短单词、结果集合
:原题: `LeetCode 0472 `_
:重点: 目标词必须由至少两个较短单词完整拼接、单词可重复使用、不能使用目标词自身作为唯一组成部分
题目重述
--------
给定互不相同的非空小写单词数组 ``words``,返回其中所有拼接词。拼接词必须能够由数组中的至少两个较短单词首尾连接而成,并且拼接后恰好覆盖目标词的全部字符。
组成单词可以重复使用,例如一个目标词可以由同一个较短单词拼接多次。目标词不能只用自身一次来证明成立。``words.length`` 位于 ``[1, 10^4]``,单词长度位于 ``[1, 30]``,全部单词字符总数不超过 ``10^5``。结果顺序不限。
自建示例
--------
包含重复使用组成词:
.. code-block:: text
输入:words = ["cat", "dog", "catdog", "dogcat", "catcat"]
输出:["catdog", "dogcat", "catcat"]
解释:前两个结果分别由 cat 和 dog 的不同顺序拼接;catcat 使用单词 cat 两次。
没有拼接词:
.. code-block:: text
输入:words = ["red", "blue", "green"]
输出:[]
解释:任一单词都无法由数组中的至少两个较短单词完整组成。
按长度加入字典并做前缀切分
--------------------------
先按单词长度排序。判断当前单词时,集合中只包含已经处理过的单词,因而不会把当前单词自身作为唯一组成部分;对当前字符串做动态规划,``reachable[i]`` 表示前 ``i`` 个字符能由集合中的单词拼出。若 ``reachable[i]`` 为真且 ``word[i..j)`` 在集合中,就把 ``reachable[j]`` 设为真。
当 ``reachable[length]`` 为真时,至少经过了两个较短单词;判断结束后再把当前单词放入集合,供更长的单词使用。单词可重复使用,因为同一个集合单词可以在不同的切分位置被查到。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findAllConcatenatedWordsInADict(
std::vector& words) {
std::sort(words.begin(), words.end(),
[](const std::string& left, const std::string& right) {
return left.size() < right.size();
});
std::unordered_set dictionary;
std::vector result;
for (const std::string& word : words) {
int n = static_cast(word.size());
std::vector reachable(n + 1, false);
reachable[0] = true;
for (int begin = 0; begin < n; ++begin) {
if (!reachable[begin]) continue;
for (int end = begin + 1; end <= n; ++end) {
if (dictionary.count(word.substr(begin, end - begin))) {
reachable[end] = true;
}
}
}
if (reachable[n]) result.push_back(word);
dictionary.insert(word);
}
return result;
}
};
代码分析
--------
按长度处理保证组成词短于当前目标,避免“自身一次匹配”造成假阳性;布尔状态的每次转移都对应一个真实的单词边界,所以终点可达就代表完整拼接。设最大单词长度为 ``L``,哈希查找平均常数时总时间约为 ``O(sum |word| * L^2)``(包含子串构造),额外空间为 ``O(sum |word|)``。