My sol with hashset grouped by word len (400 ms)


  • 0
    S

    Group the word into a series of hashset with same length. Then for each word check if substr can be found in hashset of the same length.

    class Solution {
      public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            unordered_map<int, unordered_set<string>> dict;
            int minLen = INT_MAX;
            for (string& word : words) {
                int sz = word.size();
                if (sz == 0) continue;
                minLen = min(minLen, sz);
                dict[sz].insert(word);
            }
            vector<string> res;
            for (string& word : words) {
                if (word.size() == 0) continue;
                if (isConcatenate(dict, minLen, word, 0)) {
                    res.push_back(word);
                }
            }
            return res;
        }
    private:
        bool isConcatenate(unordered_map<int, unordered_set<string>>& dict, int minLen, string& word, int pos) {
            if (pos == word.size()) return true;
            int upper = pos == 0 ? (int) word.size() - minLen : (int) word.size() - pos;
            for (int len = minLen; len <= upper; len++) {
                if (dict[len].find(word.substr(pos, len)) == dict[len].end()) continue;
                if (isConcatenate(dict, minLen, word, pos + len)) return true;
            }
            return false;
        }
    };
    

Log in to reply
 

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