Simple C++ 199ms hash map solution (no tries and no dp)


  • 2
    Y

    I am so surprised that this simple (kind of brute force) solution can work that good. It basically puts every word into a hash map and then checks if sub-component of each word existed in the hash map recursively.

    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            unordered_map<string,bool> dic;
            for (int i=0;i<words.size();i++) {
                dic[words[i]]=true;
            }
            
            vector<string> res;
            for (int i=0;i<words.size();i++) {
                if (isConcatenated(words[i],dic,false)) res.push_back(words[i]);
            }
            return res;
        }
        
        bool isConcatenated(string word, unordered_map<string,bool>& dic, bool compareWholeWord) {
            if (word.size()==0) return compareWholeWord;
            if (compareWholeWord&&dic.count(word)>0) return dic[word];
            for (int len=1;len<word.size();len++) {
                if (dic.count(word.substr(0,len))>0&&dic[word.substr(0,len)]) {
                    if (isConcatenated(word.substr(len),dic,true)) {
                        dic[word]=true;
                        return true;
                    }
                } 
            }
            return false;
        }
    };
    

  • 1
    H

    Why map? the values are never changed in your code. Use unordered_set is enough.

    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            unordered_set<string> dic(words.begin(), words.end());
            vector<string> res;
            for (int i = 0; i < words.size(); i++) {
                if (isConcatenated(words[i], dic, false)) res.push_back(words[i]);
            }
            return res;
        }
        
        bool isConcatenated(string word, unordered_set<string>& dic, bool isSubstr) {
            if (word.empty()) return isSubstr;
            if (isSubstr && dic.count(word)) return true;
            for (int len=1;len<word.size();len++) {
                if (dic.count(word.substr(0, len)) && isConcatenated(word.substr(len), dic, true)) {
                    return true;
                } 
            }
            return false;
        }
    };
    

  • 0
    Y

    @Hcisly

    You are right! It is not necessary to use map. Thanks for pointing it out.


  • 0

    You could save more time by adding the previously computed strings into the set.

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> list = new ArrayList<String>();
        Set<String> set = new HashSet(Arrays.asList(words));
    
        for(String word : words) {
            set.remove(word);
            if(dfs(word, set, "")) list.add(word);
            set.add(word);
        }
        return list;
    }
    
    private boolean dfs(String word, Set<String> set, String previous) {
        if(!previous.equals("")) set.add(previous);
        if(set.contains(word)) return true;
        
        for(int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0,i);
            if(set.contains(prefix) && 
                dfs(word.substring(i,word.length()), set, previous+prefix)) {
                return true;
            }
        }
        return false;
    }

  • 0
    Z

    I made an improvement to make the recursion loop easier to understand. Everytime if we check a word in set, we remove the word first then add it back, thus the recursion loop is easier.

    bool findHelp(string words,const unordered_set<string>& b)
    {
        if(b.count(words))
            return true;
        
        for(int i=1;i<=words.size();i++)
        {
            if(b.count(words.substr(0,i))&&findHelp(words.substr(i,words.size()-i), b))
                return true;
        }
        
        return false;
    }
    
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words)
    {
        vector<string> result;
        unordered_set<string> data;
        
        for(int i=0;i<words.size();i++)
            data.insert(words[i]);
        
        
        for(int i=0;i< words.size();i++)
        {
            data.erase(words[i]);
            if(findHelp(words[i],data))
                result.push_back(words[i]);
            data.insert(words[i]);
        }
        
        return result;
    }

Log in to reply
 

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