Java

import java.util.HashSet;
import java.util.Set;

/**

 720. Longest Word in Dictionary

 Given a list of strings words representing an English Dictionary,
 find the longest word in words that can be built one character at a time by other words in words.

 If there is more than one possible answer, return the longest word with the smallest lexicographical order.
 If there is no answer, return the empty string.

 Example 1:
 Input:
 words = ["w","wo","wor","worl", "world"]
 Output: "world"
 Explanation:
 The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

 Example 2:
 Input:
 words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 Output: "apple"
 Explanation:
 Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

 Note:
     All the strings in the input will only contain lowercase letters.
     The length of words will be in the range [1, 1000].
     The length of words[i] will be in the range [1, 30].

 @tag-trie

 */

public class Longest_Word_in_Dictionary {

    // add full implementation for visibility
    class Solution_Trie {

        public String longestWord(String[] words) {

            if (words == null || words.length == 0) {
                return "";
            }

            String result = "";
            Trie wordTrie = new Trie();

            for (String word: words) {
                wordTrie.insert(word);
            }

            for (String word: words) {

                // && higher than ||
                if (word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) {
                    boolean good = true;
                    for (int k = 1; k < word.length(); ++k) {
                        if (!wordTrie.search(word.substring(0, k))) {
                            good = false;
                            break;
                        }
                    }
                    if (good) {
                        result = word;
                    }
                }
            }
            return result;
        }

        class Trie {

            // just remember, root is the very top of this tree, all starts at root's children-array
            public TrieNode root = new TrieNode();

            // @note:@memorize: iteration is better than recursion during trie building
            public void insert(String word) {
                TrieNode node = root;
                for (char c : word.toCharArray()) {
                    if (node.children[c - 'a'] == null) {
                        node.children[c - 'a'] = new TrieNode();
                    }
                    node = node.children[c - 'a'];
                }
                node.item = word;
            }

            public boolean search(String word) {
                TrieNode node = root;
                for (char c : word.toCharArray()) {
                    if (node.children[c - 'a'] == null)
                        return false;
                    node = node.children[c - 'a'];
                }
                if (node.item.equals(word)) {
                    return true;
                } else {
                    return false;
                }
            }

            public boolean startsWith(String prefix) {
                TrieNode node = root;
                for (char c : prefix.toCharArray()) {
                    if (node.children[c - 'a'] == null)
                        return false;
                    node = node.children[c - 'a'];
                }
                return true;
            }
        }

        class TrieNode {

            // maybe 26 is not sufficient enough...I would make it 256 for general usage
            // public TrieNode[] children = new TrieNode[26];
            public TrieNode[] children = new TrieNode[256];

            public String item = "";

        }
    }

    class Solution {
        public String longestWord(String[] words) {

            if (words == null || words.length == 0) {
                return "";
            }

            String result = "";
            Set<String> wordset = new HashSet();

            for (String word: words) {
                wordset.add(word);
            }

            for (String word: words) {

                // && higher than ||
                if (word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) {
                    boolean good = true;
                    for (int k = 1; k < word.length(); ++k) {
                        if (!wordset.contains(word.substring(0, k))) {
                            good = false;
                            break;
                        }
                    }
                    if (good) result = word;
                }
            }
            return result;
        }
    }

}

Java

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        String longestWord = "";
        int maxLength = 0;
        Set<String> set = new HashSet<String>();
        int length = words.length;
        for (int i = 0; i < length; i++) {
            String word = words[i];
            int wordLength = word.length();
            if (wordLength == 1 || set.contains(word.substring(0, wordLength - 1))) {
                if (wordLength > maxLength || wordLength == maxLength && word.compareTo(longestWord) < 0) {
                    longestWord = word;
                    maxLength = wordLength;
                }
                set.add(word);
            }
        }
        return longestWord;
    }
}

All Problems

All Solutions