连接词

标签: 深度优先搜索 字典树 数组 字符串 动态规划

难度: Hard

给你一个 不含重复 单词的字符串数组 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
  • 1 <= words[i].length <= 30
  • words[i] 仅由小写英文字母组成。 
  • words 中的所有字符串都是 唯一 的。
  • 1 <= sum(words[i].length) <= 105

Submission

运行时间: 132 ms

内存: 30.4 MB

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        if len(words) == 1:
            return []
        s = set(words)
        # 测试用例42有空string。。。
        if "" in s:
            s.remove("")
        min_word_length = min([len(w) for w in words])
        @lru_cache()
        def dfs(word):
            for i in range(min_word_length, len(word) - min_word_length + 1):
                if word[:i] in s and (word[i:] in s or dfs(word[i:])):
                    return True
            return False
        ans = []
        for w in words:
            if dfs(w):
                ans.append(w)
        return ans

Explain

该题解采用DFS的思路来判断一个单词是否为连接词。对于每个单词，枚举其所有可能的分割点，如果分割点左右两部分都在单词集合中，或者左边部分在单词集合中且右边部分可以进一步分割成多个在单词集合中的子串，那么该单词就是一个连接词。为了避免重复计算，使用lru_cache对dfs函数进行记忆化搜索。

时间复杂度: O(n*l^2)

空间复杂度: O(n*l)

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        if len(words) == 1:
            return []
        s = set(words)
        # 排除空字符串
        if "" in s:
            s.remove("")
        min_word_length = min([len(w) for w in words])
        
        @lru_cache()
        def dfs(word):
            # 枚举分割点
            for i in range(min_word_length, len(word) - min_word_length + 1):
                # 如果左右两部分都在单词集合中，或者左边部分在且右边部分可以进一步分割
                if word[:i] in s and (word[i:] in s or dfs(word[i:])):
                    return True
            return False
        
        ans = []
        for w in words:
            if dfs(w):
                ans.append(w)
        return ans

Explore

DFS（深度优先搜索）适用于此问题因为它能有效地探索所有可能的单词分割方式，直到找到有效的连接词为止。DFS通过尝试每一个可能的分割点来检查是否能将单词完整地分解为已知单词的组合，这种方法对于处理具有多种可能子结构的问题非常适用。相比之下，其他算法如BFS（广度优先搜索）或动态规划在这种类型的问题中可能会涉及更多不必要的重复计算，特别是在单词长度很长时。

使用lru_cache进行记忆化搜索的主要考虑是减少重复计算和优化递归操作的性能。在这个问题中，同一个子串可能在不同的分割点被多次递归调用。通过使用lru_cache，我们可以存储已经计算过的子串结果，当再次遇到相同的子串时可以直接使用缓存结果，从而避免重复的计算。这大大提高了算法的效率，尤其是在单词集合中存在较长的单词或是单词长度分布不均匀时。

这样设定分割点范围的原因是确保分割出的两部分单词都至少达到单词集合中的最小长度，这样才有可能每一部分都是有效的单词。如果分割点小于`min_word_length`，则左侧部分会太短，无法形成有效单词；同理，如果分割点大于`len(word) - min_word_length`，则右侧部分会太短。因此，这种范围设置确保了每次分割都是有意义的，能够有效地利用单词集合中的最小单词长度来避免无效的递归调用。

在单词数组中存在大量重复单词时，首先应该将单词数组转换为集合（Set），这样可以自动去除重复的单词，减少后续处理的负担。使用集合还可以提高单词查找的效率，因为集合（通常基于哈希表实现）的平均查找时间是常数时间复杂度（O(1)）。此外，通过使用集合，我们确保每个单词只被处理一次，从而优化整体的时间和空间效率。