来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/concatenated-words

题目描述

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

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

 

示例 1：

输入：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" 组成。

示例 2：

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

提示：

1 <= words.length <= 104
0 <= words[i].length <= 1000
words[i] 仅由小写字母组成
0 <= sum(words[i].length) <= 105

解题思路

这道题还是挺复杂的，啃了一天才做出来。

首先要了解什么是字典树，字典树就是一棵前缀树，相同前缀的字符串会位于同一棵字典树的不同分支，本题主要思路就是先将所有单词按照单词长度升序排序。然后依次遍历单词，使用dfs的方法判断 单词是否是由字典树上的单词构成的，若是，则是连接词，如果不是，则将这个单词加入连接词。

字典树是一颗多叉树，这里没有用传统的多叉树的存储形式，而是在每个结点中使用了vector记录所有子树结点构成了一颗多叉树。结点中使用char来记录连接到这个结点的边，边的值就是字母。并且用一个标志位记录当前词在words中位置。

添加字典树结点的部分过程是从顶到底遍历字典树，并且遍历单词中每个字母，判断是否可以找到相同的路径使得路径上的字母和单词相同，如果没有就在分歧点新增入结点。

dfs过程则是利用深度优先找是否路径使得路径上的字母和单词相同的过程。

代码展示

class Solution {
public:
    class DictionaryTree
    {
    public:
        char mcEdge;
        int miEnd = -1;
        vector<DictionaryTree*> mvzChildren;
    };

    int AddDictionaryTreeNode(DictionaryTree* vzDictionaryTree, string s, int index)
    {
        DictionaryTree* p = vzDictionaryTree;
        for(auto c:s)
        {
            bool bFinded = false;
            for(int i = 0; i < p->mvzChildren.size(); i++)
            {
                if(p->mvzChildren[i]->mcEdge == c)
                {
                    p = p->mvzChildren[i];
                    bFinded = true;
                    break;
                }
            }
            if(!bFinded)
            {
                DictionaryTree* q = new DictionaryTree;
                q->mcEdge = c;
                p->mvzChildren.push_back(q);
                p = q;
            }
        }
        p->miEnd = index;
        return 0;
    }

    bool dfs(DictionaryTree* vzDictionaryTree, string s, int start)
    {
        if (s.length() == start) {
            return true;
        }
        DictionaryTree* p = vzDictionaryTree;
        for (int i = start; i < s.length(); i++) {
            char ch = s[i];
            bool bFind = false;
            int iIndex = 0;
            for(; iIndex < p->mvzChildren.size(); iIndex++)
            {
                if(p->mvzChildren[iIndex]->mcEdge == ch)
                {
                    bFind = true;
                    break;
                }
            }
            if (!bFind) {
                return false;
            }
            p = p->mvzChildren[iIndex];
            if (p->miEnd != -1) {
                if (dfs(vzDictionaryTree, s, i + 1)) 
                {
                    return true;
                }
            }
        }
        return false;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> vstrRet;
        sort(words.begin(), words.end(), [](string a, string b) -> bool { return a.size() < b.size();});
        DictionaryTree zDictionaryTree;
        for(int is = 0; is < words.size(); is++)
        {
            if(words[is].size() == 0)
                continue;
            if(dfs(&zDictionaryTree, words[is], 0))
            {
                vstrRet.push_back(words[is]);
            }
            else
            {
                AddDictionaryTreeNode(&zDictionaryTree, words[is], is);
            }
        }
        return vstrRet;
    }
};

 

运行结果