英文原文
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Example 2:
Input: words = ["cat","dog","catdog"] Output: ["catdog"]
Constraints:
1 <= words.length <= 1040 <= words[i].length <= 1000words[i]consists of only lowercase English letters.0 <= sum(words[i].length) <= 105
中文题目
给你一个 不含重复 单词的字符串数组 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 <= 1040 <= words[i].length <= 1000words[i]仅由小写字母组成0 <= sum(words[i].length) <= 105
通过代码
高赞题解
思路:
思路一：字典树
把所有单词建成字典树，然后用DFS让每个单词在这课字典树上跑，看是否由多个单词组成
思路二： 用哈希
- 按单词长度递增排序
- 分布判断每个单词是否由前面单词短组成
判断方法有多种，还有一些优化！
代码都很好理解
代码:
思路一：
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
trie = {}
for word in words:
if not word: continue
cur = trie
for w in word:
cur = cur.setdefault(w, {})
cur["#"] = "#" # 结束标志
res = []
def dfs(word, idx, cnt, cur):
if idx == len(word):
# 组成个数 > 2, 并且以#结束的
if cnt >= 1 and "#" in cur:
return True
return False
if "#" in cur:
if dfs(word, idx, cnt + 1, trie):
return True
if word[idx] not in cur:
return False
if dfs(word, idx + 1, cnt, cur[word[idx]]):
return True
return False
for word in words:
# 参数分别为, 单词word, 位置idx, 目前为止有几个单词组成了cnt, 字典树trie
if dfs(word, 0, 0, trie):
res.append(word)
return res
思路二：
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words.sort(key=len)
min_len = max(1, len(words[0]))
prev = set()
res = []
"""
方法1 动态规划方法判断
def check(word, prev):
if not prev: return False
n = len(word)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if not dp[j]: continue
if word[j:i] in prev:
dp[i] = True
break
return dp[-1]
"""
"""
# 方法2, DFS吧
# def check(word):
# if not prev: return False
# if not word: return True
# for i in range(1, len(word) + 1):
# if word[:i] in prev and check(word[i:]):
# return True
# return False
"""
# 方法3, 加了一个长度限制, 速度加快很多
def check(word):
if word in prev: return True
for i in range(min_len, len(word) - min_len + 1):
if word[:i] in prev and check(word[i:]):
return True
return False
for word in words:
if check(word):
res.append(word)
prev.add(word)
return res
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6982 | 17803 | 39.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 单词拆分 II | 困难 |
