पायथन में सूची में शब्द संयोजनों की संख्या गिनने का कार्यक्रम है

मान लीजिए हमारे पास स्ट्रिंग्स की एक सूची है; हमें उन शब्दों की संख्या ज्ञात करनी है जो सूची में अन्य शब्दों के संयोजन हैं। हम शब्दों का पुन:उपयोग कर सकते हैं जब कई बार संयोजित और संयोजित करते हैं।

इसलिए, यदि इनपुट शब्द =["हैलो", "वर्ल्ड", "हेलोवर्ल्ड", "प्रसिद्ध", "विश्व प्रसिद्ध", "प्रोग्रामिंग"] जैसा है, तो आउटपुट 2 होगा, क्योंकि "हेलोवर्ल्ड" का संयोजन है " हैलो" और "दुनिया"। "विश्व प्रसिद्ध" "विश्व" और "प्रसिद्ध" का संयोजन है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• कोशिश करें:=एक नया नक्शा
• शब्दों में प्रत्येक शब्द के लिए, करें
  • परत :=ट्राई
  • शब्द में प्रत्येक w के लिए, करें
    • यदि w परत में नहीं है, तो
      • परत[w] :=एक नया नक्शा
    • परत :=परत[w]
  • परत["*"] :=एक खाली टपल
  • एक फ़ंक्शन को परिभाषित करें dfs() । यह शब्द लेगा, num_concatenated_words
  • परत :=ट्राई
  • शब्द में प्रत्येक अनुक्रमणिका i और शब्द w के लिए, करते हैं
    • यदि "*" परत में है, तो
      • यदि dfs (शब्द [सूचकांक i से अंत तक], num_concatenated_words + 1) सत्य है, तो
        • सही लौटें
      • यदि w परत में नहीं है, तो
        • झूठी वापसी
    • परत :=परत[w]
  • यदि "*" परत में है और num_concatenated_words>=1 है, तो
    • सही लौटें
  • झूठी वापसी
  • मुख्य विधि से, निम्न कार्य करें:
  • गिनती :=0
  • शब्दों में प्रत्येक शब्द के लिए, करें
    • गिनती:=गिनती + dfs(शब्द, 0)
• वापसी की संख्या

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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