编写 Python 程序以计算列表中有多少个单词是其他单词的连接

假设我们有一个字符串列表。我们需要找到其他单词连接的数量。我们可以重复使用单词并连接任意次数。

因此，如果输入如下 words = [“hello”, “world”, “helloworld”, “famous”, “worldfamous”, “programming”]，则输出将为 2，因为 “helloworld” 是由 “hello” 和 “world” 连接而成，而 “worldfamous” 是由 “world” 和 “famous” 连接而成。

要解决此问题，我们将遵循以下步骤：

• trie := 一个新的映射
• 对于 words 中的每个单词，执行以下操作
  • layer := trie
  • 对于单词中的每个 w，执行以下操作
    • 如果 w 不在层中，则
    • layer[w] := 一个新的映射
    • layer := layer[w]
  • layer[“*”] := 一个空元组
  • 定义一个函数 dfs()，将它接收 word 和 num_concatenated_words。
  • layer := trie
  • 对于单词中的每个索引 i 和 w，执行以下操作
    • 如果 “*” 在层中，则
    • 如果 dfs(word[i: 结束], num_concatenated_words + 1) 为 True，则
      • 返回 True
    • 如果 w 不在层中，则
      • 返回 False
    • layer := layer[w]
  • 如果 “*” 在层中且 num_concatenated_words >= 1，则
    • 返回 True
  • 返回 False
  • 从 main 方法执行以下操作：
  • 计数 := 0
  • 对于 words 中的每个单词，执行以下操作
    • 计数 := 计数 + dfs(word, 0)
• 返回计数

让我们看下面的实现以更好地理解：

更多Python相关文章，请阅读：Python 教程

示例

class Solution:
   def solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
              layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
        layer = trie

        for i, w in enumerate(word):
          if "*" in layer:
            if dfs(word[i:], num_concatenated_words + 1):
               return True
          if w not in layer:
            return False
          layer = layer[w]

        if "*" in layer and num_concatenated_words >= 1:
          return True
        return False

      count = 0
      for word in words:
        count += dfs(word, 0)
      return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

输入

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

输出

2