Python程序：统计列表中单词串联的数量

假设我们有一个字符串列表；我们需要找到列表中哪些单词是由列表中其他单词串联而成的。在串联时可以重复使用单词，并且可以进行任意次数的串联。

例如，如果输入是words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]，则输出为2，因为"helloworld"是"hello"和"world"的串联。"worldfamous"是"world"和"famous"的串联。

为了解决这个问题，我们将遵循以下步骤：

  • trie := 一个新的映射
  • 对于words中的每个单词，执行以下操作：
    • layer := trie
    • 对于单词中的每个字符w，执行以下操作：
      • 如果layer中不存在w，则：
        • layer[w] := 一个新的映射
      • layer := layer[w]
    • layer["*"] := 一个空元组
    • 定义一个函数dfs()。它将接收单词和已串联单词数作为参数。
    • layer := trie
    • 对于单词中的每个索引i和字符w，执行以下操作：
      • 如果layer中存在"*"，则：
        • 如果dfs(word[从索引i到结尾], num_concatenated_words + 1)为True，则：
          • 返回True
        • 如果layer中不存在w，则：
          • 返回False
      • layer := layer[w]
    • 如果layer中存在"*"且已串联单词数>=1，则：
      • 返回True
    • 返回False
    • 在主方法中，执行以下操作：
    • count := 0
    • 对于words中的每个单词，执行以下操作：
      • count := count + dfs(word, 0)
  • 返回count

让我们看下面的实现来更好地理解。

示例

在线演示

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

更新于: 2020年11月26日

浏览量：131

启动您的职业生涯

通过完成课程获得认证

开始学习
广告