720. Longest Word in Dictionary.md

720. Longest Word in Dictionary

---

Difficulty : Easy

Related Topics : HashTable、Trie

---

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

• mine
  • Java

    • Runtime: 29 ms, faster than 24.28%, Memory Usage: 39.1 MB, less than 75.79% of Java online submissions

      public String longestWord(String[] words) {
          Set<String> set = new HashSet<>();
          for (String w : words) {
              set.add(w);
          }
          Arrays.sort(words, (o1, o2) -> o1.length() - o2.length());
          String res = "";
          for (int j = words.length - 1; j >= 0; j--) {
              String w = words[j];
              int t = w.length();
              if (t < res.length()) break;
      
              while (t > 0) {
                  if (!set.contains(w.substring(0, t))) break;
                  t--;
              }
              if (t != 0) continue;
      
              if (res.length() < w.length()) {
                  res = w;
              } else if (res.length() == w.length()) {
                  if (res.compareTo(w) > 0) res = w;
              }
          }
          return res;
      }
      

    • Trie Runtime: 13 ms, faster than 65.84%, Memory Usage: 39.4 MB, less than 59.29% of Java online submissions

      public String longestWord(String[] words) {
          Arrays.sort(words, (o1, o2) -> {
              if (o1.length() == o2.length()) {
                  return o1.compareTo(o2);
              }
              return o1.length() - o2.length();
          });
          WTrie trie = new WTrie();
          trie.hasWord = true;
          String res = "";
          for (String w : words) {
              if (trie.insert(w) && w.length() > res.length()) {
                  res = w;
              }
          }
          return res;
      }
      
      class WTrie {
          WTrie[] next = new WTrie[26];
          boolean hasWord;
      
          boolean insert(String word) {
              char[] arr = word.toCharArray();
              WTrie cur = this;
              for (int i = 0; i < arr.length; i++) {
                  int j = arr[i] - 'a';
                  if (i + 1 != arr.length && (!cur.hasWord || cur.next[j] == null)) return false;
                  if (cur.next[j] == null) {
                      cur.next[j] = new WTrie();
                  }
                  cur = cur.next[j];
              }
              cur.hasWord = true;
              return true;
          }
      }
      

---

• the most votes

• Runtime: 5 ms, faster than 99.61%, Memory Usage: 39.9 MB, less than 32.13% of Java online submissions

  public String longestWord(String[] words) {
      Trie trie = new Trie();
      for (int i = 0; i < words.length; i++) {
          trie.add(words[i]);
      }
      return trie.dfs();
  }
  
  class Trie {
      Node root = new Node();
  
      void add(String word) {
          Node cur = this.root;
          for (int i = 0; i < word.length(); i++) {
              char ch = word.charAt(i);
              if ( cur.children[ch - 'a'] == null) {
                  cur.children[ch - 'a'] = new Node();
              }
              cur = cur.children[ch - 'a'];
          }
          cur.value = word;
      }
  
      String dfs() {
          return dfs(this.root, false);
      }
  
      String dfs(Node node, boolean skipNull) {
          if (skipNull && node.value == null) return "";
  
          String ans = node.value == null ? "" : node.value;
  
          for ( int i = 0; i < node.children.length; i++ ) {
              Node child = node.children[i];
  
              if (child != null) {
                  String subStr = dfs(child, true);
  
                  if (subStr.length() > ans.length()) {
                      ans = subStr;
                  }
              }
          }
  
          return ans;
      }
  }
  
  class Node {
      String value;
      Node[] children = new Node[26];
  }
  

---