[LC] 472. Concatenated Words

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:

Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
 "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Solution1: TLE

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        List<String> res = new ArrayList<>();
        List<String> wordList = new ArrayList<>();
        for (String str: words) {
            if (helper(str, wordList)) {
                res.add(str);
            }
            wordList.add(str);
        }
        return res;
    }
    
    private boolean helper(String str, List<String> list) {
        boolean[] boolArr = new boolean[str.length() + 1];
        for (int i = 1; i < boolArr.length; i++) {
            if (list.contains(str.substring(0, i))) {
                boolArr[i] = true;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (boolArr[j] && list.contains(str.substring(j, i))) {
                    boolArr[i] = true;
                    break;
                }
            }
        }
        return boolArr[str.length()];
    }
}

Solution2

class Solution {
    TrieNode root = new TrieNode();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = new TrieNode();
        build(words);
        for (String word: words) {
            if (search(word, 0, 0)) {
                res.add(word);
            }
        }
        return res;
    }
    
    private void build (String[] words) {
        for (String str: words) {
            if (str == null || str.length() == 0) {
                continue;
            }
            // restart cur every time
            TrieNode cur = root;
            char[] charArr = str.toCharArray();
            for (int i = 0; i < charArr.length; i++) {
                if (cur.children[charArr[i] - 'a'] == null) {
                    cur.children[charArr[i] - 'a'] = new TrieNode();
                }
                cur = cur.children[charArr[i] - 'a'];
            }
            cur.isWord = true;
        }
    }
    
    private boolean search(String word, int index, int count) {
        // restart cur every time
        TrieNode cur = root;
        for (int i = index; i < word.length(); i++) {
            if (cur.children[word.charAt(i) - 'a'] == null) {
                return false;
            }
            cur = cur.children[word.charAt(i) - 'a'];
            if (cur.isWord && search(word, i + 1, count + 1)) {
                return true;
            }
        }
        return cur.isWord && count >= 1;
    }
}

class TrieNode {
    boolean isWord;
    TrieNode[] children;
    public TrieNode () {
        isWord = false;
        children = new TrieNode[26];
    }
}