Accepted Solution using Trie Tree


  • 0
    A

    This solution used the Trie Tree to solve the problem. I think time complexity should be like buildTrie(O(n * L * 26)), add/search(O(L*n)), where n refers the number of words and L refers the length of a world.
    Please correct me if I am wrong:)

    class Solution {
        // build and implement Trie
        class TrieNode{
            boolean isLeaf = false;
            char c;
            TrieNode[] children;
            public TrieNode(char c){
                this.c = c;
                this.children = new TrieNode[26];
            }
        }
        class Trie{
            TrieNode root = new TrieNode(' ');
            public void addWord(String s){
                TrieNode p = root;
                p = root;
                for (char c: s.toCharArray()){
                    if (p.children[c - 'a'] == null){
                        p.children[c - 'a'] = new TrieNode(c);
                    }
                    p = p.children[c - 'a'];
                }
                p.isLeaf = true;
            }
    
            public boolean search(String s){
                TrieNode p = root;
                for (char c: s.toCharArray()){
                    if (p.children[c - 'a'] == null || !p.children[c - 'a'].isLeaf){
                        return false;
                    }
                    p = p.children[c - 'a'];
                }
                return p.isLeaf;
            }
        }
    
        //find the longest valid word
        public String longestWord(String[] words) {
             if (words == null || words.length == 0){
                return "";
            }
    
            Trie trie = new Trie();
            for (String s: words){
                trie.addWord(s);
            }
    
            String maxWord = "";
    
            for (String s: words){
                if (trie.search(s)){
                    if (s.length() > maxWord.length()){
                        maxWord = s;
                    } else if (s.length() == maxWord.length() && s.compareTo(maxWord) < 0){
                        maxWord = s;
                    }
                }
            }
            return maxWord;
        }
    }
    

Log in to reply
 

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