题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一组单词 words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有单词则返回空字符串。
示例：
- 输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
- 输出： "dogwalker"
- 解释： "dogwalker"可由"dog"和"walker"组成。
提示：
- 0 <= len(words) <= 200
- 1 <= len(words[i]) <= 100
题目思考
- 如何判断单词是否由其他单词组合而成?
解决方案
思路
- 分析题目, 要想求得符合要求的最长单词, 我们可以先按照题目给定的规则对单词排序 (长度降序, 相等时按照字典序升序), 这样第一个满足要求的单词就是最长单词, 无需继续检查
- 那如何检查某个单词是否是其他单词的组合呢?
- 对于当前待检查单词, 如果它的某个前缀是某个输入单词, 那么只需要保证剩余部分也是某个输入单词, 或者它也是若干单词的组合即可
- 所以这里我们可以采用记忆化搜索的思想, 引入两个参数: 当前待检查单词 w, 是否允许整体是输入单词 allowWhole
- 在检查某个单词是否是其他单词的组合时, 传入 allowWhole 是 False, 表示至少需要是其他两个单词的组合
- 然后遍历其每个分隔, 如果前缀是某个输入单词, 则只需要递归检查剩余部分, 此时传入的 allowWhole 就是 True 了, 表示剩余部分可以单独作为一个单词使用, 如果它本身就是某个输入单词, 那直接返回 True 即可
- 另外在判断某个单词是否是某个输入单词时, 我们可以将给定的单词列表转成集合, 这样能加速查找效率
- 还有可以将判断函数缓存起来 (@functools.cache), 避免重复计算, 这就是典型的记忆化的思想
- 下面代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(NlogN+NC): 假设字符串数目是 N, 平均长度是 C, 那么排序复杂度为 O(NlogN), 记忆化搜索的复杂度为 O(NC) - 空间复杂度
O(N): 单词集合和记忆化搜索占用的空间都是 O(N)
代码
class Solution:
def longestWord(self, words: List[str]) -> str:
# 先将单词列表转成集合, 加速查找效率
ws = set(words)
# 然后将单词按照长度降序排序, 长度相等时按照字典序升序排序
# 这样第一个满足要求的单词就是最长单词
words.sort(key=lambda w: (-len(w), w))
@functools.cache
def isValid(w, allowWhole):
# allowWhole表示是否允许w作为单独单词出现在集合中
# 值为False时则必须由至少两个出现在集合中的单词组合而成
if allowWhole and w in ws:
return True
for i in range(1, len(w)):
# 检查每种组合的可能性
if w[:i] in ws and isValid(w[i:], True):
return True
return False
for w in words:
if isValid(w, False):
# 当前单词可由其他单词组合得到, 为有效的最长单词, 直接返回
return w
# 没找到有效组合单词
return ""
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号