accepted Java Trie solution with explanation


  • 0
    T

    My solution includes two parts:

    1. build up a Trie with all the words from the input array.
    2. loop through the words and use the Trie to determine if a word is concatenated from the rest of words.

    For step 2, the way I archive is to find the count of sub-words recursively.
    I check if each subarray starting from index 0 is a word in the trie. if yes, I can make a recursion call to get the count of words for the rest of string.

    Notice that the last word in the count method must be a word in the Trie. if it is not a word, we should skip it.

    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Trie trie = new Trie();
            for (String word : words) {
                Trie temp = trie;
                char[] chars = word.toCharArray();
                for(char c : chars) {
                    int idx = c - 'a';
                    if(temp.children[idx] == null){
                        temp.children[idx] = new Trie();
                    }
                    temp = temp.children[idx]; 
                }
                temp.word = word;
            }
            //loop trie to fing all concatenatedWord
            List<String> result = new ArrayList<>();
            for(String word : words) {
                if(containsWords(word.toCharArray(), 0, trie) > 1){
                    result.add(word);
                }
            }
            return result;
        }
        
        private int containsWords(char[] chars, int idx, Trie trie) {
            Trie temp = trie;
            for(int i = idx; i < chars.length; i++){
                temp = temp.children[chars[i] - 'a'];
                if(temp == null){
                    break;
                }
                if(temp.word != null){
                    if(i == chars.length - 1){
                        return 1;
                    }else{
                        int next = containsWords(chars, i+1, trie);
                        if(next == 0){
                            continue;
                        }else{
                            return 1 + next;
                        }
                    }
                }
            }
            return 0;
        }
    
        class Trie {
            String word;
            Trie[] children = new Trie[26];
        }
    }
    

Log in to reply
 

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