A review of top solutions
After studying the top solutions, I might not be the only one wondering which is the best and why. So I would like to share my understanding with this post.\n\n
After studying the top solutions, I might not be the only one wondering which is the best and why. So I would like to share my understanding with this post.\n\nOne sub problem is word break. There are three ways to solve word break,[ DFS, BFS and DP](https://discuss.leetcode.com/topic/66356/evolve-from-brute-force-to-optimal). DFS is the best way because it terminates as soon as it finds one way to break the word. DP and BFS checks all the substrings thus less efficient. Combined with the sorting idea by [@shawngao ](https://discuss.leetcode.com/topic/72113/java-dp-solution) is the best I have.\n```\n    struct comp {\n        bool operator()(string &s1, string &s2) {\n            return s1.size()<s2.size();\n        }\n    };\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        unordered_set<string> ht; \n        vector<string> res;\n        sort(words.begin(),words.end(),comp());\n        for(auto &s:words) {\n            if(s.empty()) continue;\n            if(canbrk(0,s,ht)) res.push_back(s);\n            ht.insert(s);\n        }\n        return res;\n    }\n    bool canbrk(int p, string &s, unordered_set<string>& ht) {\n        int n = s.size();\n        if(p==n) return 1;\n        string sub;\n        for(int i=p;i<n;i++) if(ht.count(sub+=s[i])&&canbrk(i+1,s,ht)) return 1;\n        return 0;\n    }\n```\nAnother improve is to use trie instead of hash table to save memory. However, looks like all c++ solution with trie gets memory limit exceeded. I think the oj bug needs to be fixed @administrators \n```\n    struct Node {\n        Node():end(),nxt() {};\n        bool end;\n        Node* nxt[26];\n    };\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<string> res;\n        sort(words.begin(),words.end(),comp());\n        Node *root = new Node();\n        for(auto &s:words) {\n            if(s.empty()) continue;\n            if(canbrk(0,s,root)) res.push_back(s);\n            addWord(s,root);\n        }\n        destroy(root);\n        return res;\n    }\n    bool canbrk(int p, string &s, Node *r) {\n        int n = s.size();\n        if(p==n) return 1;\n        string sub;\n        for(int i=p;i<n;i++) if(search(sub+=s[i], r)&&canbrk(i+1,s,r)) return 1;\n        return 0;\n    }\n    void addWord(string word, Node *p) {\n        for(char c:word) {\n            Node *&nxt = p->nxt[c-'a'];\n            if(!nxt) nxt = new Node();\n            p = nxt;\n        }\n        p->end = 1;\n    }\n    bool search(string& word, Node *r) {\n        for(char c:word) {\n            Node *&nxt = r->nxt[c-'a'];\n            if(!nxt) return 0;\n            r = nxt;\n        }\n        return r->end;\n    }\n    void destroy(Node* r) {\n        if (!r) return;\n        for (int i = 0; i < 26; i++) destroy(r->nxt[i]);\n        delete r;\n    }\n```
['C']