Java Trie solution


  • 1
    D
    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> concatenated = new ArrayList<>();
            if (words == null || words.length <= 1) {
                return concatenated;
            }
            Trie root = new Trie();
            for (String word : words) {
                root.insert(word, 0);
            }
            for (String word : words) {
                if (segments(root, root, word, 0) > 1) {
                    concatenated.add(word);
                }
            }
            return concatenated;
        }
    
        private int segments(Trie root, Trie current, String word, int index) {
            if (word == null || index >= word.length()) {
                return 0;
            }
            char ch = word.charAt(index);
            if (!current.children.containsKey(ch)) {
                return 0;
            }
            
            int candidate1 = 0;
            if (current.children.get(ch).isWordEnd) {
                int recursive = segments(root, root, word, index + 1);
                candidate1 = recursive > 0 ? 1 + recursive : (index == word.length() - 1 ? 1 : 0);
            }
            if (candidate1 > 1) {
                return candidate1;
            }
            
            int candidate2 = segments(root, current.children.get(ch), word, index + 1);
            
            return Math.max(candidate1, candidate2);
        }
    
        static class Trie {
            Map<Character, Trie> children = new HashMap<>();
            boolean isWordEnd;
    
            public void insert(String str, int index) {
                if (str == null || index >= str.length()) {
                    return;
                }
                char ch = str.charAt(index);
                if (!children.containsKey(ch)) {
                    children.put(ch, new Trie());
                }
                if (index == str.length() - 1) {
                    children.get(ch).isWordEnd = true;
                }
                children.get(ch).insert(str, index + 1);
            }
        }
    }
    

Log in to reply
 

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