https://leetcode-cn.com/problems/concatenated-words/

1. 题目

2. 思路

构建一个字典树，在字典树上进行搜索，要记忆化，不然会超时

3. 题解

#include<bits/stdc++.h>
using namespace std;
class Trie {
public:
    vector<Trie*>children;
    int num;
    bool isEnd;
    char ch;
    Trie* searchPrefix(string prefix){
        Trie* node = this;
        for(char ch : prefix) {
            ch = ch - 'a';
            if(node -> children[ch] == nullptr) {
                return nullptr;
            }
            node = node -> children[ch];
        }
        return node;
    }
    Trie() : children(26),num(0),isEnd(false){}
    void insert(string word) {
        Trie* node = this;
        for(char ch : word) {
            ch -= 'a';
            if(node -> children[ch] == nullptr) {
                node -> children[ch] = new Trie;
            }
            node = node -> children[ch];
            node -> ch = ch + 'a';
        }
        node -> num = (node -> num) ++;
        node -> isEnd = true;
    }
    bool search(string word) {
        Trie* trie = this -> searchPrefix(word);
        return trie == nullptr ? false : trie -> isEnd;
    }
    bool startsWith(string prefix) {
        Trie* trie = this -> searchPrefix(prefix);
        return trie == nullptr ? false : true;
    }
};
class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string>vec;
        bool visit[10010];
        for(int i = 0 ; i < 10010 ; i ++) {
            visit[i] = false;
        }
        Trie trie;
        for(string str : words) {
            trie.insert(str);
        }
        bool flag = false;
        function<void(string &,int,int)> dfs = [&](string &s,int index,int num) -> void{
            if(index == s.length()) {
                //判断是否是单词组成的
                if(num > 1 ) {
                    flag =true;
                }
                return ;
            }
            if(visit[index]) {
                return ;
            } else {
                visit[index] = true;
            }
            Trie* p = &trie;
            for(int i = index ; i < s.length() ; i ++) {
                if(p -> children[s[i] - 'a'] != nullptr) {
                    p = p -> children[s[i] - 'a'] ;
                    if(p -> isEnd) {
                        dfs(s,i + 1,num + 1) ;
                    }
                } else {
                    break;
                }
            }
        };
        for(string str : words) {
            memset(visit,0,sizeof(visit));
            flag = false;
            dfs(str,0,0);
            if(flag) {
                vec.push_back(str);
            }
        }
        return vec;
    }
};
int main()
{
    string s = "catsandogcat";
    vector<string>wordDict{"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
    Solution solution;
    vector<string> vec = solution.findAllConcatenatedWordsInADict(wordDict);
    for(auto & it : vec) {
        cout<< it <<endl;
    }
    return 0;
}