102ms java Trie + DFS solution. With explanation, easy to understand.


  • 19
    F
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res = new ArrayList<String>();
            if (words == null || words.length == 0) {
                return res;
            }
            TrieNode root = new TrieNode();
            for (String word : words) { // construct Trie tree
                if (word.length() == 0) {
                    continue;
                }
                addWord(word, root);
            }
            for (String word : words) { // test word is a concatenated word or not
                if (word.length() == 0) {
                    continue;
                }
                if (testWord(word.toCharArray(), 0, root, 0)) {
                    res.add(word);
                }
            }
            return res;
        }
        public boolean testWord(char[] chars, int index, TrieNode root, int count) { // count means how many words during the search path
            TrieNode cur = root;
            int n = chars.length;
            for (int i = index; i < n; i++) {
                if (cur.sons[chars[i] - 'a'] == null) {
                    return false;
                }
                if (cur.sons[chars[i] - 'a'].isEnd) {
                    if (i == n - 1) { // no next word, so test count to get result.
                        return count >= 1;
                    }
                    if (testWord(chars, i + 1, root, count + 1)) {
                        return true;
                    }
                }
                cur = cur.sons[chars[i] - 'a'];
            }
            return false;
        }
        public void addWord(String str, TrieNode root) {
            char[] chars = str.toCharArray();
            TrieNode cur = root;
            for (char c : chars) {
                if (cur.sons[c - 'a'] == null) {
                    cur.sons[c - 'a'] = new TrieNode();
                }
                cur = cur.sons[c - 'a'];
            }
            cur.isEnd = true;
        }
    }
    class TrieNode {
        TrieNode[] sons;
        boolean isEnd;
        public TrieNode() {
            sons = new TrieNode[26];
        }
    

  • 0
    G
    This post is deleted!

  • 2
    L

    good idea. rewrite in java

    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res = new ArrayList<>();
            TrieNode root = makeTrie(words);
            
            for(String word : words) {
                if(word.length() == 0) continue;
                if(helper(root, word, 0)) {
                    res.add(word);
                }  
            }
            
            return res;
        }
        
        public boolean helper(TrieNode root, String word, int pos) {   
            TrieNode ws = root;
        
            for(int i = pos; i < word.length(); i++) {
                if(ws.children[word.charAt(i) - 'a'] == null) {
                    return false;
                }
                ws = ws.children[word.charAt(i) - 'a'];
                if(ws.word != null && !ws.word.equals(word)) {
                    if(helper(root, word, i + 1)) {
                        return true;
                    }
                }
            }
            return pos != 0 && ws.word != null;   
        }
        
        class TrieNode {
            String word;
            TrieNode[] children = new TrieNode[26];
        }
        
        public TrieNode makeTrie(String[] words) {
            TrieNode root = new TrieNode();
            for(String word : words) {
                TrieNode ws = root;
                for(char c : word.toCharArray()) {
                    if(ws.children[c - 'a'] == null) {
                        ws.children[c - 'a'] = new TrieNode();
                    }
                    ws = ws.children[c - 'a'];
                }
                ws.word = word;
            }
            return root;
        }
    }
    

  • 0
    A
    This post is deleted!

  • 0
    M

    whats the time complexity?
    I do not know how to calculate, could you please give me some advice


  • 0
    X

    i think using trie is essentailly even worse than brute force, brute force with a hashset is like nk^2. trie is nk for building, nk^2 for validation


  • 0
    L

    I copied this approach in python but getting a TLE. Would appreciate any help to improve the solution. Is your java solution getting accepted?

    class TrieNode(object):
        def __init__(self, char):
            self.char = char
            self.children = {}
            self.lastChar = False
                
    class Trie(object):
        def __init__(self):
            self.root = TrieNode(None)
            
        def addWord(self, word):
            node = self.root
            for c in word:
                if c not in node.children:
                    node.children[c]=TrieNode(c)
                node=node.children[c]
            node.lastChar = True
        def hasConcatWords(self, word, index, wcount):
            node = self.root
            n = len(word)
            for i in range(index, n):
                c = word[i]
                if c not in node.children:
                    return False
                if node.children[c].lastChar:
                    if i==n-1:
                        return wcount>=1
                    if self.hasConcatWords(word, i+1, wcount+1):
                        return True
                node = node.children[c]
            return False
    class Solution(object):              
        # Getting TLE on this solution.
        #
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            trie = Trie()
            res = [ ]
            for word in words:
                if len(word): trie.addWord(word)
            for word in words:
                if len(word):
                    wcount = 0
                    if trie.hasConcatWords(word, 0, wcount):
                        res.append(word)
            return res
    

Log in to reply
 

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