题目描述

Given a list of words (without duplicates

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
 "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Note:

1. The number of elements of the given array will not exceed 10,000
2. The length sum of elements in the given array will not exceed 600,000.
3. All the input string will only include lower case letters.
4. The returned elements order does not matter.

题意：给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

算法1

(哈希+搜索)

题解：我们知道一个连接词肯定是由若干个比自己短的字符串组成的，所有首先我们将字符串按照长度从小到大排序。我们使用两个哈希表hash用来存储已经遍历过的单词，res用来存储之前确定是组合词的所有答案。对于每一个单词：我们尝试将其分成两部分，如果前半部分在hash中出现，那么我们只需要判断后半部分是不是一个组合词或者也在hash中出现就可以了。

C++ 代码

class Solution {
public:
    static bool cmp(const string&a,const string &b)
    {
        return a.size() < b.size();
    }
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        int n = words.size();
        sort(words.begin(),words.end(),cmp);
        unordered_set<string> hash;
        unordered_set<string> res;
        for(auto word:words)
        {
            if(word == "") continue;
            if(dfs(word,hash,res)) res.insert(word);
            hash.insert(word);
        }
        return vector<string> (res.begin(),res.end());
    }
    bool dfs(string word,unordered_set<string>& hash,unordered_set<string>& res)
    {
        if(word == "") return true;
        if(res.find(word) != res.end()) return true;
        int len = word.length();
        for(int i = 1; i <= len ; i ++)
        {
            string cur = word.substr(0,i);
            if(hash.find(cur) != hash.end() && dfs(word.substr(i,len - i),hash,res))
                return true;
        }
        return false;
    }
};