python列表中有计算单词串联数量的程序

假设我们有一个字符串列表;我们还必须在列表中找到与其他单词串联的单词数量。连接和连接任意次数时,我们可以重用单词。

因此,如果输入像单词= [“” hello“,” world“,” helloworld“,” famous“,” worldfamous“,” programming“]]一样,则输出将为2,因为“ helloworld”是“hello”和“world”。“worldfamous”是“world”和“famous”的串联。


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

示例

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
猜你喜欢