给出一个字符串数组 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:排序+hash
class Solution {public String longestWord(String[] words) {Arrays.sort(words);Set<String>set=new HashSet<>();String res="";for(String s:words){if(s.length()==1||set.contains(s.substring(0,s.length()-1))){set.add(s);res=s.length()>res.length()?s:res;}}return res;}
}
思路2:字典树
注意和208、实现 Trie (前缀树)【中等】的search()有点区别,每个前缀都必须在trie里,所以inDictionary()中,if(cur == null || !cur.exist)时都为false
class Solution {public String longestWord(String[] words) {Arrays.sort(words);String res="";Trie trie=new Trie();for(String s:words){trie.insert(s);if(trie.inDictionary(s) && s.length()>res.length()) res=s;}return res;}
}class Trie{TrieNode root;public Trie(){root=new TrieNode();}public void insert(String s) {TrieNode cur = root;for (char c : s.toCharArray()) {if (cur.children[c - 'a'] == null) {cur.children[c - 'a'] = new TrieNode();}cur = cur.children[c - 'a'];}cur.exist = true;}public boolean inDictionary(String s) {TrieNode cur = root;for (char c : s.toCharArray()) {cur = cur.children[c - 'a'];if (cur == null || !cur.exist) {//每个前缀都必须在trie里return false;}}return cur.exist;}
}class TrieNode {boolean exist;TrieNode[] children;TrieNode() {exist = false;children = new TrieNode[26];}
}










