TLE for last before test case - Help


  • 0
    V

    Hi,
    I have done a DFS solution with some caching. I get a TLE for the last before test case( with all a's). Please let me know what is wrong here.

    Thanks,
    Vignesh

    class Solution {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            vector<string> concatWords;
            if(words.size() <= 1) {
                return concatWords;
            }
            unordered_set<string> dictionary = populateDictionary(words);
            int count=0;
            for(int i=0; i<words.size(); i++) {
                unordered_map<int, int> cache;
                string checker="";
                count = countWords(0, words[i], checker, dictionary, cache);
                if(count > 1) {
                    concatWords.push_back(words[i]);
                }
            }
            return(concatWords);
        }
        
        unordered_set<string> populateDictionary(vector<string>& words) {
            unordered_set<string> dict;
            for(int i=0; i<words.size(); i++) {
                if(dict.find(words[i]) == dict.end()) {
                    dict.insert(words[i]);
                }
            }
            return(dict);
        }
        
        int countWords(int pos, string word, string checker, unordered_set<string> &dictionary, unordered_map<int, int> cache) {
            if(pos >= word.length()) {
                if(dictionary.find(checker) != dictionary.end()) {
                    return 1;
                }
                return 0;
            }
            if(cache.find(pos) != cache.end()) {
                return(cache[pos]);
            }
            int count=0;
            int ret = 0;
            string newCh="";
            checker.push_back(word[pos]);
            if(dictionary.find(checker) == dictionary.end()) {
                count = countWords(pos+1, word, checker, dictionary, cache);
            } else {
                count = 1 + countWords(pos+1, word, newCh, dictionary, cache);
                if( count == 1) {
                    count = countWords(pos+1, word, checker, dictionary, cache);
                }
            }
            cache[pos] = count;
            return(count);
        }
    };
    

Log in to reply
 

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