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


  • 14
    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!

  • 1
    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;
        }
    }
    

Log in to reply
 

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