难度: Medium
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： ["cat","banana","dog","nana","walk","walker","dogwalker"] 输出： "dogwalker" 解释： "dogwalker"可由"dog"和"walker"组成。
提示：
0 <= len(words) <= 2001 <= len(words[i]) <= 100运行时间: 23 ms
内存: 16.1 MB
class Solution:
def longestWord(self, words: List[str]) -> str:
words.sort(key=lambda x: (-len(x), x))
def recursive(word, array):
if not word:
return True
for x in array:
if word[:len(x)] == x:
if recursive(word[len(x):], array):
return True
return False
for i, word in enumerate(words):
if recursive(word, words[i + 1:]):
return word
return ""
这个题解使用了递归的方法来检查一个单词是否可以由其他单词组成。首先，对输入的单词列表进行排序，排序规则是先按照单词长度降序排列，长度相同的情况下按字典序升序排列。这样做的目的是为了先检查最长的单词，以及在长度相同的情况下，优先检查字典序较小的单词。接着，遍历排序后的单词列表，对每个单词使用递归函数来判断它是否可以由列表中其他的单词组成。递归函数的基本思路是：如果当前单词为空，表示已经成功找到了一种组合方式，返回True；否则，遍历单词列表中剩余的单词，检查当前单词是否以列表中的某个单词开头，如果是，则递归地检查去掉开头后剩余部分的单词是否也可以由列表中的单词组成。如果遍历完所有剩余的单词都没有找到合适的组合，则返回False。如果找到了一个可以由其他单词组成的最长单词，就直接返回这个单词，否则返回空字符串。
时间复杂度: O(nlogn + n^2 * m)
空间复杂度: O(m)
class Solution:
def longestWord(self, words: List[str]) -> str:
words.sort(key=lambda x: (-len(x), x)) # 对单词列表按长度降序、字典序升序排序
def recursive(word, array):
if not word: # 递归基准情况：如果当前单词为空，返回True
return True
for x in array:
if word[:len(x)] == x: # 检查当前单词是否以列表中的某个单词开头
if recursive(word[len(x):], array): # 递归检查剩余部分
return True
return False
for i, word in enumerate(words): # 遍历单词列表
if recursive(word, words[i + 1:]): # 检查每个单词是否可以由其他单词组成
return word
return "" # 如果没有符合条件的单词，返回空字符串
这种排序策略能够确保程序首先尝试使用最长的单词来形成解答，这是因为题目要求找到可以由其他单词组成的“最长单词”。通过这样的排序，程序可以优先检查较长的单词是否可以由其他单词组成，从而更快地找到可能的最长解。此外，字典序升序排列确保了在有多个长度相同的单词可以作为答案时，返回字典顺序最小的一个，满足题目对输出格式的要求。
在递归函数中处理这种情况时，递归会持续进行，直到当前单词为空。对于'nananana'这类由'nana'重复组成的单词，每次递归都会切割掉'nana'的部分，再对剩余部分进行相同的操作。这种情况可能会导致递归调用次数显著增加，从而影响程序的运行效率。为了优化这一点，可以使用动态规划或记忆化递归来存储已经计算过的中间结果，避免重复计算，从而提高效率。
根据题解的逻辑，一旦递归检查剩余部分返回True，说明当前单词已经成功地被其他单词组成，因此可以直接结束当前的递归调用返回True，无需继续检查其他可能的组合。这种方法可以减少不必要的递归调用，提高算法的效率。如果继续检查，可能会导致大量不必要的计算，从而降低算法性能。