472. 连接词
给你一个 不含重复 单词的字符串数组
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 <= 104
0 <= words[i].length <= 1000
words[i]仅由小写字母组成
0 <= sum(words[i].length) <= 105
通过次数10,444提交次数23,881
法 1 内置hash + 动态规划
思路
挨个检查每个单词是否可以由别的单词组成。
具体的检查方法，采用动态规划。
但是此处不能用bool型来判断。因为会认为自己本身也是由自己构成的，所以采用num判断该单词由几个别的单词组成。
题解
class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: if len(words) <= 2: return [] hash_set = set(words) # 检查字符串是否可由别的子串组成 def check(word): word = "#" + word dp = [-1 for _ in range(len(word))] dp[0] = 0 # dp[i] 以 i 结尾的能由几个别的单词组成 # word[j:i+1] 是否在words中 for i in range(1, len(word)): for j in range(i, 0, -1): if dp[j-1]>-1 and word[j:i+1] in hash_set: dp[i] = dp[j-1] + 1 break return dp[-1] > 1 res = [] for word in words: if check(word): res.append(word) return res
法2 字符串hash + 动态规划
思路
同法1 ，但是采用字符串hash来判断word中每个子串 是否是别的word
题解
class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: BASE = 31 MOD = 10 ** 11 hash_set = set() for word in words: word_hash = 0 for char in word: word_hash = (word_hash * BASE + ord(char)) % MOD hash_set.add(word_hash) def check(word): dp = [-1 for _ in range(len(word)+1)] dp[0] = 0 for i in range(0, len(word)+1): if dp[i] == -1: continue cur_hash = 0 for j in range(i+1, len(word)+1): cur_hash = (cur_hash * BASE + ord(word[j-1])) % MOD if cur_hash in hash_set: dp[j] = max(dp[j], dp[i]+1) if dp[len(word)] > 1: return True return False res = [] for word in words: if check(word): res.append(word) return res