题目描述

给定一个 不含重复 单词的字符串数组 words，编写一个程序，返回 words 中的所有 连接词。

连接词 的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

样例

输入：
words = ["cat","cats","catsdogcats","dog",
"dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出：["catsdogcats","dogcatsdog","ratcatdogcat"]

解释：
"catsdogcats"由"cats", "dog" 和 "cats"组成; 
"dogcatsdog"由"dog", "cats"和"dog"组成; 
"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。

输入：words = ["cat","dog","catdog"]
输出：["catdog"]

说明

• 1 <= words.length <= 10^4
• 0 <= words[i].length <= 1000
• words[i] 仅由小写字母组成。
• 0 <= sum(words[i].length) <= 10^5

算法1

(哈希表，动态规划) $O(Tn^2)$

1. 将所有单词先加入哈希表，接下来逐一枚举判断单词是否为拼接而成的。
2. 对于一个单词 s，设状态 $f(i)$ 表示 s 的前 $i$ 个字符是否可以被单词拼接表示，这里的有效下标从 $1$ 开始。
3. 初始时，$f(0) = true$，其余为 $false$。
4. 转移时，对于一个已经计算好的位置 $i$ 且 $f(i)$ 为 $true$
   • 从 $i + 1$ 枚举 $j$，直到 $n - 1$，过程中累计哈希值和累加字符串，通过哈希表判断当前哈希值和字符串是否存在。
   • 如果 $i > 0$，则可以考虑 $j = n$ 的情况，此时如果发现 $f(n) = true$，则直接返回 $true$。

时间复杂度

• 预处理哈希表需要 $O(Tn)$ 的时间，这里的 $T$ 为单词的个数，$n$ 为单个字符串的最大长度。
• 动态规划的状态数为 $O(n)$，每次转移共有 $O(n)$ 个位置，判断字符串是否为单词在哈希良好的情况下只需要常数的时间。
• 故动态规划的时间复杂度为 $O(n^2)$。
• 判断 $T$ 个单词，共需要 $O(Tn^2)$ 的时间复杂度。

空间复杂度

• 需要 $O(Tn)$ 的额外空间存储哈希表。

C++ 代码

#define ULL unsigned long long
const int base = 131;

class Solution {
private:
    unordered_map<ULL, vector<string>> h;

    void insert(const string &s) {
        ULL v = 0;
        for (char c : s)
            v = v * 131 + c;

        h[v].push_back(s);
    }

    bool find(ULL v, const string &s) {
        if (h.find(v) == h.end())
            return false;

        for (const string &w : h[v])
            if (w == s)
                return true;

        return false;
    }

    bool check(const string &s) {
        const int n = s.size();
        vector<bool> f(n + 1, false);

        f[0] = true;
        for (int i = 0; i < n; i++) {
            if (!f[i])
                continue;

            ULL v = 0;
            string t;
            for (int j = i + 1; j < n; j++) {
                v = v * base + s[j - 1];
                t += s[j - 1];
                if (!f[j] && find(v, t))
                    f[j] = true;
            }

            v = v * base + s[n - 1];
            t += s[n - 1];

            if (i > 0 && find(v, t))
                return true;
        }

        return false;
    }

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        for (const string &s : words)
            insert(s);

        vector<string> ans;
        for (const string &s : words)
            if (check(s))
                ans.push_back(s);

        return ans;
    }
};

算法2

(字典树，动态规划) $O(Tn^2)$

1. 将所有单词先加入字典树。
2. 动态规划和算法 1 一样，但枚举 $j$ 的过程中，使用字典树辅助判断。
   • 从 $i + 1$ 枚举 $j$，直到 $n - 1$，过程中通过字典树跳转。
   • 如果发现当前位置是一个字符串的结束位置，则当前位置转移为 $true$。
   • 如果发现无法跳转，则说明当前位置即之后的位置都无法拼接，可以直接终止循环。

时间复杂度

• 预处理字典树需要 $O(Tn)$ 的时间，这里的 $T$ 为单词的个数，$n$ 为单个字符串的最大长度。
• 动态规划的状态数为 $O(n)$，每次转移共有 $O(n)$ 个位置，使用字典树判断字符串只需要常数时间。
• 故动态规划的时间复杂度为 $O(n^2)$
• 判断 $T$ 个单词，共需要 $O(Tn^2)$ 的时间复杂度。

空间复杂度

• 需要 $O(Tn)$ 的额外空间存储字典树。

C++ 代码

const int T = 100010;

struct Node {
    int nxt[26];
    bool word;
    Node() {
        memset(nxt, 0, sizeof(nxt));
        word = false;
    }
};

class Solution {
private:
    int cnt, rt;
    Node node[T];

    void insert(const string &s) {
        int p = rt;
        for (char c : s) {
            if (!node[p].nxt[c - 'a'])
                node[p].nxt[c - 'a'] = ++cnt;
            p = node[p].nxt[c - 'a'];
        }

        node[p].word = true;
    }

    bool check(const string &s) {
        const int n = s.size();
        vector<bool> f(n + 1, false);

        f[0] = true;
        for (int i = 0; i < n; i++) {
            if (!f[i])
                continue;

            int p = rt;
            bool flag = true;
            for (int j = i + 1; j < n; j++) {
                if (!node[p].nxt[s[j - 1] - 'a']) {
                    flag = false;
                    break;
                }

                p = node[p].nxt[s[j - 1] - 'a'];
                if (node[p].word)
                    f[j] = true;
            }

            if (!flag)
                continue;

            p = node[p].nxt[s[n - 1] - 'a'];
            if (i > 0 && p > 0 && node[p].word)
                return true;
        }

        return false;
    }

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        cnt = 0;
        rt = ++cnt;

        for (const string &s : words)
            insert(s);

        vector<string> ans;
        for (const string &s : words)
            if (check(s))
                ans.push_back(s);

        return ans;
    }
};