All Concat Words

no_optimization.js

var findAllConcatenatedWordsInADict = function(words) {
    words.sort((a, b) => a.length - b.length);
    
    let wordSet = new Set();
    words.forEach(word => {
        // Use Trie
        if (word) wordSet.add(word);
    });
    
    // DFS
    function DFS(searchWord, searchSet) {
        if (searchWord === '') return true;
        
        return Array.from(searchSet).some(word => {
            if (searchWord.startsWith(word)) {
                const remainingWord = searchWord.substr(word.length, searchWord.length);
                if (remainingWord === '') return true;
                return DFS(remainingWord, searchSet);
            }
        });
    }
    
    const validWords = [];
    wordSet.forEach(word => {
        const currentSet = new Set(wordSet);
        currentSet.delete(word);
        if (DFS(word, currentSet)) {
            validWords.push(word);
        }
    });
    return validWords;
};

sorted.js

var findAllConcatenatedWordsInADict = function(words) {
    // words.sort((a, b) => a.length - b.length);
    const wordsByLength = {};
    
    let wordSet = new Set();
    words.forEach(word => {
        if (!word) return;
        
        wordSet.add(word);
        
        const length = word.length;
        if (length in wordsByLength === false) {
            wordsByLength[length] = [];
        }
        wordsByLength[length].push(word);
    });
    
    const validWords = [];
    
    const lengthKeys = Object.keys(wordsByLength).sort((a, b) => Number(a) - Number(b));
    lengthKeys.forEach((length, i) => {
        wordsByLength[length].forEach(word => {
            const searchKeys = lengthKeys.slice(0, i + 1);
            const searchWords = new Set(searchKeys.reduce((arr, length) => {
                return arr.concat(wordsByLength[length]);
            }, []));
            searchWords.delete(word);
            
            if (DFS(word, searchWords)) validWords.push(word);
        });
    });
    
    return validWords;
    
    // DFS
    function DFS(searchWord, searchSet) {
        if (searchWord === '') return true;
        
        return Array.from(searchSet).some(word => {
            if (searchWord.startsWith(word)) {
                const remainingWord = searchWord.substr(word.length, searchWord.length);
                if (remainingWord === '') return true;
                return DFS(remainingWord, searchSet);
            }
        });
    }
};