连接词 - C++力扣472题

题目链接：https://leetcode.com/problems/concatenated-words/description/

解题思路

这个题目难度算是困难偏下吧，其实想清楚了要怎么做就很好解决，很多人看到字符串就会开始毫无头绪（正是在下），其实我们只需要把字符串理解成字符的数组有时候可能就会有办法了。

这题其实我们可以先把词全部录入到一个集合里面，然后再对每个词进行检验。检验的方式其实也很简单，其实就是 dfs 的方法，首先先从左边找到第一个连接词，剩下的那一段扔进函数再找，一直找到底如果返回的都是 true ，那很明显这个就符合我们题目的条件了。

完整代码：

class Solution {
public:

    bool checkConcatenate(string word, set<string> &s) {
        for(int i = 1; i < word.size(); i++) {
            string left = word.substr(0, i), right = word.substr(i, word.size() - i);
            
            if(s.find(left) != s.end() && (s.find(right) != s.end() || checkConcatenate(right, s))) return true;
        }
        return false;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> ans;
        set<string> s;
        for(string word : words) s.insert(word);
        for(string word : words) {
            if(checkConcatenate(word, s)) {
                ans.push_back(word);
            }
        }

        return ans;
    }
};