LeetCode 题解工作台
连接词
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。 连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。 示例 1： 输入： words = ["cat","cats","catsdogcats","dog"…
6
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
判断一个单词是不是连接词，需要判断这个单词是否完全由至少两个给定数组中的更短的非空单词（可以重复）组成。判断更短的单词是否在给定数组中，可以使用字典树实现。 首先将 按照字符串的长度递增的顺序排序，排序后可以确保当遍历到任意单词时，比该单词短的单词一定都已经遍历过，因此可以根据已经遍历过的全部单词判断当前单词是不是连接词。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。
示例 1：
输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成;
"dogcatsdog" 由 "dog", "cats" 和 "dog" 组成;
"ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2：
输入：words = ["cat","dog","catdog"] 输出：["catdog"]
提示：
1 <= words.length <= 1041 <= words[i].length <= 30words[i]仅由小写英文字母组成。words中的所有字符串都是 唯一 的。1 <= sum(words[i].length) <= 105
解题思路
方法一：前缀树 + DFS
判断一个单词是不是连接词，需要判断这个单词是否完全由至少两个给定数组中的更短的非空单词（可以重复）组成。判断更短的单词是否在给定数组中，可以使用字典树实现。
首先将 按照字符串的长度递增的顺序排序，排序后可以确保当遍历到任意单词时，比该单词短的单词一定都已经遍历过，因此可以根据已经遍历过的全部单词判断当前单词是不是连接词。
在将 排序之后，遍历 ，跳过空字符串，对于每个非空单词，判断该单词是不是连接词，如果是连接词则将该单词加入结果数组，如果不是连接词则将该单词加入字典树。
判断一个单词是不是连接词的做法是在字典树中深度优先搜索。从该单词的第一个字符（即下标 处的字符）开始，在字典树中依次搜索每个字符对应的结点，可能有以下几种情况：
- 如果一个字符对应的结点是单词的结尾，则找到了一个更短的单词，从该字符的后一个字符开始搜索下一个更短的单词；
- 如果一个字符对应的结点在字典树中不存在，则当前的搜索结果失败，回到上一个单词的结尾继续搜索。
如果找到一个更短的单词且这个更短的单词的最后一个字符是当前单词的最后一个字符，则当前单词是连接词。由于数组 中没有重复的单词，因此在判断一个单词是不是连接词时，该单词一定没有加入字典树，由此可以确保判断连接词的条件成立。
说明：由于一个连接词由多个更短的非空单词组成，如果存在一个较长的连接词的组成部分之一是一个较短的连接词，则一定可以将这个较短的连接词换成多个更短的非空单词，因此不需要将连接词加入字典树。
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, w):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
def dfs(w):
if not w:
return True
node = trie
for i, c in enumerate(w):
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
if node.is_end and dfs(w[i + 1 :]):
return True
return False
trie = Trie()
ans = []
words.sort(key=lambda x: len(x))
for w in words:
if dfs(w):
ans.append(w)
else:
trie.insert(w)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(M ^ 3 \cdot N) |
| 空间 | O(N \cdot M) |
面试官常问的追问
外企场景- question_mark
Check if the candidate understands how to use dynamic programming and recursion together to optimize the search for concatenated words.
- question_mark
Look for knowledge of optimizing searches using trie data structures and recognizing when to use them for large-scale problems.
- question_mark
Assess if the candidate can handle word manipulations effectively, considering time and space complexities in relation to the problem's constraints.
常见陷阱
外企场景- error
Not using a trie to optimize substring lookups, which can lead to inefficient solutions for large inputs.
- error
Failing to properly handle words that can overlap, leading to incorrect results.
- error
Using brute force methods without considering time complexity, which will lead to performance issues when the input list is large.
进阶变体
外企场景- arrow_right_alt
Implementing this problem using only dynamic programming without a trie.
- arrow_right_alt
Allowing a word to be formed from any subset of words (not just at least two) in the list.
- arrow_right_alt
Handling edge cases where a word might be a concatenation of its own prefix and suffix.