Trie + BFS solution. O(Nm)


  • 0
    S

    It's the same idea as found in the Solution. But this is implemented in BFS where you don't need to check for alphabetical ordering...

    class Solution {
        TrieNode root;
        
        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            StringBuilder prefix;
            
            TrieNode() {
                children = new TrieNode[26];
                isWord = false;
                prefix = new StringBuilder();
            }
        }
        
        void buildTrie(String word) {
            TrieNode curr = root;
            
            for (int i = 0; i < word.length(); i++) {
                int c = word.charAt(i) - 'a';
                if (curr.children[c] == null) {
                    curr.children[c] = new TrieNode();
                    curr.children[c].prefix.append(curr.prefix);
                    curr.children[c].prefix.append(word.charAt(i));
                }
                curr = curr.children[c];
            }
            
            curr.isWord = true;
        }
        
        public String longestWord(String[] words) {
            root = new TrieNode();
            root.isWord = true;
            
            for (String s : words) {
                buildTrie(s);
            }
            
            LinkedList<TrieNode> q = new LinkedList<TrieNode>();
            q.addLast(root);
            String result = "";
            
            while (!q.isEmpty()) {
                TrieNode node = q.removeFirst();
                if (!node.isWord) continue;
                String word = node.prefix.toString();
                
                if (word.length() >= result.length()) {
                    result = word;
                } 
                
                for (int i = node.children.length - 1; i >= 0; i--) {
                    if (node.children[i] != null) { 
                        q.addLast(node.children[i]); 
                    }
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

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