AC C++ DP Solution (532 ms), unordered_map + unordered_set.


  • 0
    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            sort(words.begin(), words.end(), [](const string& s1, const string& s2){
                return s1.length() < s2.length();
            });
            vector<string> res;
            for (auto s : words) {
                wordDict.insert(s);
                dict[s[0]].emplace_back(s);
            }
            for (auto s : words) {
                if (dfs(s)) res.emplace_back(s);    
            }
            return res;
        }
        
        bool dfs(const string& s) {
            if (s.empty()) return false;
            if (found.find(s) != found.end()) return found[s];
            bool res = false;
            for (auto const &ss : dict[s[0]]) {
                int len = ss.length();
                if (len < s.length()) {
                    if (ss != s.substr(0, len)) continue;
                    string rem = s.substr(len);
                    if (wordDict.find(rem) != wordDict.end()) res = true;
                    else res |= dfs(rem);
                }
                else break;
                if (res) break;
            }
            found[s] = res;
            return res;
        }
        
        unordered_set<string> wordDict;
        unordered_map<char, vector<string>> dict;
        unordered_map<string, bool> found;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.