最长单词
难度:
标签:
题目描述
Given a list of words, write a program to find the longest word made of other words in the list. If there are more than one answer, return the one that has smallest lexicographic order. If no answer, return an empty string.
Example:
Input: ["cat","banana","dog","nana","walk","walker","dogwalker"] Output: "dogwalker" Explanation: "dogwalker" can be made of "dog" and "walker".
Note:
0 <= len(words) <= 2001 <= len(words[i]) <= 100
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/*
思路：
1. 将单词按照长度从短到长进行排序。
2. 使用一个集合来存储已经处理过的单词。
3. 遍历每个单词，检查它是否可以由集合中的其他单词组成。
4. 如果可以组成，则更新结果。如果有多个长度相同的结果，选择字典序最小的。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public String longestWord(String[] words) {
List<String> wordList = Arrays.stream(words).sorted((a, b) -> a.length() == b.length() ? a.compareTo(b) : a.length() - b.length()).collect(Collectors.toList());
Set<String> wordSet = new HashSet<>();
String[] result = {""};
wordList.forEach(word -> {
if (canForm(word, wordSet)) {
if (word.length() > result[0].length() || (word.length() == result[0].length() && word.compareTo(result[0]) < 0)) {
result[0] = word;
}
}
wordSet.add(word);
});
return result[0];
}
private boolean canForm(String word, Set<String> wordSet) {
if (wordSet.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] && wordSet.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}
解释
方法:
这个题解使用了递归的方法来检查一个单词是否可以由其他单词组成。首先，对输入的单词列表进行排序，排序规则是先按照单词长度降序排列，长度相同的情况下按字典序升序排列。这样做的目的是为了先检查最长的单词，以及在长度相同的情况下，优先检查字典序较小的单词。接着，遍历排序后的单词列表，对每个单词使用递归函数来判断它是否可以由列表中其他的单词组成。递归函数的基本思路是：如果当前单词为空，表示已经成功找到了一种组合方式，返回True；否则，遍历单词列表中剩余的单词，检查当前单词是否以列表中的某个单词开头，如果是，则递归地检查去掉开头后剩余部分的单词是否也可以由列表中的单词组成。如果遍历完所有剩余的单词都没有找到合适的组合，则返回False。如果找到了一个可以由其他单词组成的最长单词，就直接返回这个单词，否则返回空字符串。
时间复杂度:
O(nlogn + n^2 * m)
空间复杂度:
O(m)
代码细节讲解
🦆
为什么在排序单词时选择先按长度降序然后按字典序升序进行？这样的排序策略对解决问题有什么具体帮助？
▷🦆
在递归函数中，如果当前单词是由另一个单词重复组成（例如'nananana'由'nana'组成），这种情况如何处理？是否会影响递归的终止条件或效率？
▷🦆
递归函数中，若递归检查剩余部分返回True，是否就直接结束整个递归，还是继续检查其他可能的组合？这会如何影响算法的性能？
▷