TrieTree Method


  • 0
    T
    class Solution {
        class TrieNode{
            TrieNode[] childs = new TrieNode[26];
            String str;
            TrieNode(){
                
            }
        }
        
        public void addWord(TrieNode root,String word){
            TrieNode current = root;
            for(char c:word.toCharArray()){
                if(current.childs[c-'a']==null){
                    current.childs[c-'a'] = new TrieNode();
                }
                current = current.childs[c-'a'];
            }
            current.str = word;
        }
       
        int maxlen = 0;
        public String longestWord(String[] words) {
            TrieNode root = new TrieNode();
            for(String ele:words){
                addWord(root,ele);
            }
            
            Set<String> set = new HashSet<>();
            
            for(int i=0;i<26;i++){
                if(root.childs[i]!=null){
                    dfs(set,root.childs[i],1);
                }
            }
            
            List<String> list = new ArrayList<String>(set);
            Collections.sort(list);
            return list.get(0);
        }
        
        public void dfs(Set<String> set,TrieNode root,int len){
            if(root==null || root.str==null){
                return;
            }
            
            if(len>maxlen && root.str!=null){
                set.clear();
                set.add(root.str);
                maxlen = len;
            }else if(len==maxlen && root.str!=null){
                set.add(root.str);
            }
            
            for(int i=0;i<26;i++){
                dfs(set,root.childs[i],len+1);
            }
        }
        
        
    }
    

  • 3
    C

    @tiandiao123
    We can sort words first and then get the longest word while building the Trie. Share my code below.

    class Solution {
        class TrieNode {
    		public boolean isWord;
    		public TrieNode[] next = new TrieNode[26];
    	}
    
    	boolean addWord(TrieNode root, String word) {
    		TrieNode p = root;
    		boolean canDone = true;
    		for (char ch : word.toCharArray()) {
    			if (!p.isWord)
    				canDone = false;
    			if (p.next[ch - 'a'] == null) {
    				p.next[ch - 'a'] = new TrieNode();
    			}
    			p = p.next[ch - 'a'];
    		}
    		p.isWord = true;
    		return canDone;
    	}
    
        public String longestWord(String[] words) {
    		String res = "";
    		Arrays.sort(words);
    		TrieNode root = new TrieNode();
    		root.isWord = true;
    
    		for (String word : words) {
    			boolean canDone = addWord(root, word);
    			if (canDone && word.length() > res.length())
    				res = word;
    		}
    		return res;
        }
    }
    

  • 3
    L

    Python solution using Trie:

    class TrieNode(object):
        def __init__(self):
            self.children = collections.defaultdict(TrieNode)
            self.word = ''
    
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
    
        def add(self, word):
            curr = self.root
            for c in word: 
                curr = curr.children[c]
            curr.word = word
    
        def dfs(self):
            stack = self.root.children.values()
            ans = ''
            while stack:
                node = stack.pop()
                if len(node.word) == 0: continue
                if len(node.word) > len(ans) or (len(node.word) == len(ans) and node.word < ans):
                    ans = node.word
                stack += node.children.values()
            return ans
    
    class Solution(object):
        def longestWord(self, words):
            trie = Trie()
            for word in words: trie.add(word)
            return trie.dfs()
    

Log in to reply
 

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