My Java Solution DFS + Trie 97% what is the solutions in the head !! little one..


  • 1
    T
    /**
         * Trie + DFS
         * */
        class TrieNode {
            boolean isLeaf = false;
            TrieNode[] next;
            TrieNode(){
                next = new TrieNode[26];
            }
        }
    
        class Trie {
            TrieNode root;
    
            Trie() {
                root = new TrieNode();
            }
            /**
             * @param word :the word to be inserted
             * @param i :the index of the pos of analyse combination
             * @param n1 :the point to analyse the construction of the word
             * @param count :the most number of the word it can consists of
             * */
            public boolean search(String word, int i, TrieNode n1, int count) {
                if (i == word.length() && count >= 2) {
                    return true;
                }
                for (; i < word.length(); i ++) {
                    int k = word.charAt(i) - 'a';
                    if (n1.next[k] != null) {
                        if (n1.next[k].isLeaf) {
                            if (search(word, i + 1, root, count + 1)) {
                                return true;
                            }
                        }
                        n1 = n1.next[k];
                    }else {
                        if (count == 0) break;
                        return false;
                    }
                }
                return false;
    
            }
    
            public void insert (String word) {
                TrieNode p = root;
                for (int i = 0 ; i < word.length(); i ++) {
                    int k = word.charAt(i) - 'a';
                    if (p.next[k] == null) {
                        p.next[k] = new TrieNode();
                    }
                    p = p.next[k];
                }
                p.isLeaf = true;
            }
        }
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
           Arrays.sort(words, new Comparator<String>() {
               @Override
               public int compare(String o1, String o2) {
                   return o1.length() - o2.length();
               }
           });
    
            Trie trie = new Trie();
            List<String> res = new ArrayList<>();
            for (String str : words) {
                if (trie.search(str, 0,trie.root, 0 )){
                    res.add(str);
                }
                trie.insert(str);
            }
            return res;
        }
    

Log in to reply
 

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