720. Longest Word in Dictionary – Using modified Trie

https://leetcode.com/problems/longest-word-in-dictionary/

In this problem, we build a Trie, and then we traverse it and try to get the leaf with the longest word. A simple twist is that, at every node, we only traverse further to a child if and only if the child is a word node, meaning it corresponds to a word existed in the dictionary.

In Java:

static class Solution {
    public String longestWord(String[] words) {
        //Build Trie
        Trie trie = new Trie();
        trie.buildTrie(words);
        return trie.getLongestWord();
    }

    public class Trie {
        private TrieNode root;

        protected class TrieNode {
            HashMap<Character, TrieNode> next;
            String word;

            protected TrieNode() {
                next = new HashMap<>();
            }
        }

        public TrieNode buildTrie(String[] words) {
            root = new TrieNode();
            for (String w : words) {
                TrieNode p = root;
                for (char c : w.toCharArray()) {
                    if (!p.next.containsKey(c)) p.next.put(c, new TrieNode());
                    p = p.next.get(c);
                }
                p.word = w;
            }
            return root;
        }

        HashMap<TrieNode, String> memoryMap = new HashMap<>();

        public String dfs(TrieNode node) {
            if (memoryMap.containsKey(node)) {
                return memoryMap.get(node);
            }
            if (node == null) {
                return "";
            }
            if (node.next.size() == 0) {
                //This is a leaf node
                return node.word;
            }
            String result = node.word!=null?node.word:"";
            for (TrieNode t : node.next.values()) {
                if (t.word != null) {
                    //valid child
                    String s = dfs(t);
                    result = result.length() > s.length()?
                            result: result.length()<s.length()?
                            s: result.compareTo(s) < 0 ? result : s;
                }
            }
            memoryMap.put(node, result);
            return result;
        }

        public String getLongestWord() {
            return dfs(root);
        }
    }
}

In Kotlin

class Solution {
        fun longestWord(words: Array<String>): String? {
            //Build Trie
            val trie = Trie()
            trie.buildTrie(words)
            return trie.longestWord
        }

        inner class Trie {
            private var root = TrieNode()

            var memoryMap = HashMap<TrieNode, String>()

            val longestWord: String?
                get() = dfs(root)

            inner class TrieNode() {
                var next: HashMap<Char, TrieNode> = HashMap()
                var word: String? = null
            }

            fun buildTrie(words: Array<String>): TrieNode {
                for (w in words) {
                    var p: TrieNode = root
                    for (c in w.toCharArray()) {
                        p.next.computeIfAbsent(c) {TrieNode()}
                        p = p.next[c]!!
                    }
                    p.word = w
                }
                return root
            }

            fun dfs(node: TrieNode?): String {
                if (memoryMap.containsKey(node)) {
                    return memoryMap[node]!!
                }
                if (node == null) {
                    return ""
                }
                if (node.next.size == 0) {
                    //This is a leaf node
                    return node.word?:""
                }
                var result = node.word?:""
                for (t in node.next.values) {
                    if (t.word != null) {
                        //valid child
                        val s = dfs(t)
                        result = if (result.length > s.length)
                            result
                        else if (result.length < s.length)
                            s
                        else if (result < s) result else s
                    }
                }
                memoryMap[node] = result
                return result
            }
        }
    }
}