Java solution using Trie and DFS with Stack


  • 0
    B

    Build a trie using the input.
    Store the word at the terminal node.
    Do DFS and continue if the value of the node is != from null
    Choose solution

    class Solution {
            class TrieNode {
                private String value = null;
                private Map<Character, TrieNode> children = new HashMap<>();
    
                @Override
                public String toString() {
                    return value + " " + children;
                }
            }
    
            class Trie {
                private TrieNode root = new TrieNode();
    
                public void insert(String word) {
                    TrieNode current = root;
                    for (int i = 0; i < word.length(); i++) {
                        TrieNode nextTrie = current.children.get(word.charAt(i));
                        if (nextTrie == null) {
                            nextTrie = new TrieNode();
                            current.children.put(word.charAt(i), nextTrie);
                        }
                        if (i == word.length() - 1) {
                            nextTrie.value = word;
                        }
                        current = nextTrie;
                    }
                }
    
                public String findLongestWord() {
                    String solution = "";
                    int maxLen = -1;
                    Stack<TrieNode> traversalStack = new Stack<>();
                    traversalStack.push(root);
                    while (!traversalStack.isEmpty()) {
                        TrieNode current = traversalStack.pop();
                        if (current.value != null) {
                            if (current.value.length() > maxLen) {
                                maxLen = current.value.length();
                                solution = current.value;
                            } else if (current.value.length() == maxLen &&
                                    current.value.compareTo(solution) < 0) {
                                solution = current.value;
                            }
                        }
                        current.children.entrySet().stream()
                            .filter(characterTrieNodeEntry -> characterTrieNodeEntry.getValue().value != null)
                            .forEach(characterTrieNodeEntry -> traversalStack.push(characterTrieNodeEntry.getValue()));
                    }
                    return solution;
                }
            }
    
            public String longestWord(String[] words) {
                Trie t = new Trie();
                Arrays.stream(words).forEach(t::insert);
                return t.findLongestWord();
            }
        }
    

Log in to reply
 

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