题目描述
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入：["cat","banana","dog","nana","walk","walker","dogwalker"]输出："dogwalker"解释："dogwalker"可由"dog"和"walker"组成。
代码实现
import java.util.*; class Solution { public String longestWord(String[] words) { // 按长度分组 Map<Integer, List<String>> map = new HashMap<>(); Set<String> set = new HashSet<>(); int maxL = 0; for (String s : words) { set.add(s); int k = s.length(); map.computeIfAbsent(k, key -> new ArrayList<>()).add(s); maxL = Math.max(maxL, k); } // 从最长到最短检查 while (maxL > 0) { if (map.containsKey(maxL)) { List<String> list = map.get(maxL); Collections.sort(list); // 字典序排序 for (String s : list) { set.remove(s); // 先移除当前单词 if (canBeFormed(s, set)) { return s; } set.add(s); // 恢复 } } maxL--; } return ""; } private boolean canBeFormed(String word, Set<String> dict) { if (word.isEmpty()) return false; boolean[] dp = new boolean[word.length() + 1]; dp[0] = true; for (int i = 1; i <= word.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.contains(word.substring(j, i))) { dp[i] = true; break; } } } return dp[word.length()]; } }class Solution { public String longestWord(String[] words) { // 1. 对单词数组进行排序 // 规则：优先按长度降序排列（从长到短），长度相同时按字典序升序排列 Arrays.sort(words, (o1, o2) -> { if (o1.length() == o2.length()) // 长度相同时，按字典序升序排列（a在前，z在后） return o1.compareTo(o2); else { // 长度不同时，按长度降序排列（长在前，短在后） return Integer.compare(o2.length(), o1.length()); } }); // 2. 创建HashSet存储所有单词，便于快速查找 Set<String> set = new HashSet<>(Arrays.asList(words)); // 3. 遍历排序后的单词数组 // 由于已经按长度降序、字典序升序排序，找到的第一个符合条件的单词就是答案 for (String word : words) { // 3.1 先将当前单词从集合中移除，确保不会使用单词本身来构造自己 set.remove(word); // 3.2 检查当前单词是否能由集合中的其他单词组成 if (find(set, word)) return word; // 找到符合条件的单词，直接返回 // 3.3 恢复集合，准备检查下一个单词 set.add(word); } // 4. 没有找到符合条件的单词，返回空字符串 return ""; } // 递归方法：判断给定的单词是否能由字典（set）中的单词组成 public boolean find(Set<String> set, String word) { // 基线条件：如果单词长度为0，说明已经成功匹配完成 if (word.length() == 0) return true; // 尝试所有可能的分割点 for (int i = 0; i < word.length(); i++) { // 将单词分为两部分：word[0...i] 和 word[i+1...end] String prefix = word.substring(0, i + 1); // 如果前缀存在于字典中，并且剩余部分也能由字典中的单词组成 if (set.contains(prefix) && find(set, word.substring(i + 1))) return true; // 找到一种有效的分割方式 } // 所有分割方式都尝试过了，无法组成该单词 return false; } }
