720. Longest Word in Dictionary

###Question 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].

Solution

  1. Trie Tree:
    • Need to sort to keep the lexicographical order.
    • If the string contains only one character and that one is empty in tree, save.
    • If string contains multiple characters and [0, len - 2] exists, it has a chance to update the result.
    • The point is how I can come up with the trie tree. Since we are comparing character one by one, trie tree has its benefit that we can check the nodes. 
       class Solution {
  private static class Node{
      Node[] childs;
      boolean isLeaf;
      public Node(){
          this.childs = new Node[26];
      }
  }
  private void insert(Node node, String s){
      char[] arr = s.toCharArray();
      if(arr.length == 1){
          node.childs[arr[0] - 'a'] = new Node();
          if(len < 1){
              this.res = s;
              this.len = 1;
          }
          node = node.childs[arr[0] - 'a'];
          node.isLeaf = true;
      }else{
          for(int i = 0; i < arr.length - 1; i++){
              int c = arr[i] - 'a';
              if(node.childs[c] == null){
                  return;
              }
              node = node.childs[c];
          }
          if(node.isLeaf){
              node.childs[arr[arr.length - 1] - 'a'] = new Node();
              node = node.childs[arr[arr.length - 1] - 'a'];
              node.isLeaf = true;
              if(arr.length > len){
                  this.res = s;
                  len = arr.length;
              }
          }
      }
  }
  private String res = "";
  private int len = 0;
  public String longestWord(String[] words) {
      Arrays.sort(words);
      Node root = new Node();
      for(String word : words){
          insert(root, word);
      }
      return res;
  }
 }