720. Longest Word in Dictionary

/**
Using Trie.
Save all the words in Trie.
Now for each word check if there is an end after each character.

Time Complexity = O(n * l)
n = Number of words.
l = Average length of the words.

Space Complexity = O(n * l)
*/
class Solution {
    class TrieNode {
        HashMap<Character, TrieNode> map;
        boolean isEnd;

        TrieNode() {
            map = new HashMap<>();
            isEnd = false;
        }
    }

    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode cur = root;
            for (char c : w.toCharArray()) {
                if (!cur.map.containsKey(c)) {
                    cur.map.put(c, new TrieNode());
                }
                cur = cur.map.get(c);
            }
            cur.isEnd = true;
        }

        String result = "";

        for (String w : words) {
            if (result.length() > w.length() || (result.length() == w.length() && result.compareTo(w) < 0)) {
                continue;
            }

            TrieNode cur = root;

            for (char c : w.toCharArray()) {
                cur = cur.map.get(c);
                if (!cur.isEnd) {
                    break;
                }
            }

            if (cur.isEnd) {
                result = w;
            }
        }
        return result;
    }
}

/**
Sort the words alphabetically, therefore shorter words always comes before longer words.
Iterate over the sorted list, populate the words that can be built in the HashSet. Any prefix of a word must comes before that word. If not, then ignore the word.

Time Complexity = O(n*l * log(n)) - Sort the words array. and iterate over each character to find the result
n = Number of words.
l = Average length of the words.

Space Complexity = O(n * l)
*/
// class Solution {
//     public String longestWord(String[] words) {
//         if (words == null || words.length == 0) {
//             return "";
//         }
//         if (words.length == 1) {
//             if (words[0].length() == 1) {
//                 return words[0];
//             } else {
//                 return "";
//             }
//         }

//         Arrays.sort(words);

//         HashSet<String> set = new HashSet<>();
//         String result = "";

//         for (String w : words) {
//             if (w.length() == 1 || set.contains(w.substring(0, w.length()-1))) {
//                 set.add(w);
//                 if (w.length() > result.length()) {
//                     result = w;
//                 }
//             }
//         }
//         return result;
//     }
// }