Java 25ms using Trie


  • 0
    A
    class Solution {
        
        class TrieNode {
            char letter;
            TrieNode[] next = new TrieNode[26];
            boolean isWord;
            
            TrieNode(char letter) {
                this.letter = letter;
            }
        }
        
        public String longestWord(String[] words) {
            TrieNode root = new TrieNode(' ');
            for(String word : words) {
                TrieNode iter = root;
                for(int i = 0; i < word.length(); ++i) {
                    int thisLetterPos = word.charAt(i) - 'a';
                    if(iter.next[thisLetterPos] == null) iter.next[thisLetterPos] = new TrieNode(word.charAt(i));
                    iter = iter.next[thisLetterPos];
                }
                iter.isWord = true;
            }    
            root.isWord = true;
            return getMaxString(root, "").substring(1);
        }
        
        private String getMaxString(TrieNode root, String curr) {
            if(!root.isWord) return null;
            curr += root.letter;
            String result = "";
            for(int i = 25; i >= 0; --i) {
                if(root.next[i] == null) continue;
                String s = getMaxString(root.next[i], curr);
                if(s != null) result = s.length() >= result.length() ? s : result; 
            }
            return result.length() > curr.length() ? result : curr;
        }
        
    }

Log in to reply
 

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