给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

示例 1：

输入：words = [“w”,”wo”,”wor”,”worl”, “world”]
输出：”world”
解释： 单词”world”可由”w”, “wo”, “wor”, 和 “worl”逐步添加一个字母组成。
示例 2：

输入：words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]
输出：”apple”
解释：”apply” 和 “apple” 都能由词典中的单词组成。但是 “apple” 的字典序小于 “apply”

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 30
所有输入的字符串 words[i] 都只包含小写字母。

  1. class Solution {
  2.     Set<String> set = new HashSet<>();
  3.     public String longestWord(String[] words) {
  4.         for (String s : words) set.add(s);
  5.         String res = "";
  6.         for (String s : words) {
  7.             if (s.length() >= res.length() && check(s)) {
  8.                 if (s.length() == res.length()) {
  9.                     //比较字典序
  10.                     String tem = "";
  11.                     for (int i = 0; i < s.length(); ++i) 
  12.                         if (s.charAt(i) < res.charAt(i)) {
  13.                             tem = s;
  14.                             break;
  15.                         } else if (s.charAt(i) > res.charAt(i)) {
  16.                             tem = res;
  17.                             break;
  18.                         }
  19.                     res = tem;
  20.                 } else res = s;
  21.             }
  22.         }
  23.         return res;
  24.     }
  26.     private boolean check(String s) {
  27.         if (s.length() == 1 && set.contains(s)) return true;
  28.         String tem = s.substring(0, s.length() - 1);
  29.         boolean res = false;
  30.         if (set.contains(tem)) 
  31.             res = check(tem);
  32.         return res;
  33.     }
  34. }

前缀树

  1. class Solution {
  2.     class TreeNode {
  3.         TreeNode[] node = new TreeNode[26];
  4.         boolean isWord;
  5.     }
  7.     TreeNode root = new TreeNode();
  9.     private void add(String s) {
  10.         TreeNode p = root;
  11.         for (int i = 0 ; i < s.length(); ++i) {
  12.             int u = s.charAt(i) - 'a';
  13.             if (p.node[u] == null) p.node[u] = new TreeNode();
  14.             p = p.node[u];
  15.         }
  16.         //标记结尾
  17.         p.isWord = true;
  18.     }
  20.     public String longestWord(String[] words) {
  21.         for (String s : words) add(s);
  22.         String res = "";
  23.         for (String s : words) {
  24.             int n = res.length(), m = s.length();
  25.             if (m < n) continue;
  26.             if (m == n && s.compareTo(res) > 0) continue;
  27.             if (search(s)) res = s;
  28.         }
  29.         return res;
  30.     }
  32.     private boolean search(String s) {
  33.         TreeNode p = root;
  34.         for (int i = 0; i < s.length(); ++i) {
  35.             int tem = s.charAt(i) - 'a';
  36.             if (p.node[tem] == null || p.node[tem].isWord == false) 
  37.                 return false;
  38.             p = p.node[tem];
  39.         }
  40.         return p != null && p.isWord;
  41.     }   
  42. }