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

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

उदाहरण के लिए, यदि इनपुट words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"] है, तो आउटपुट 2 होगा, क्योंकि "helloworld" "hello" और "world" का कन्कैटनेशन है। "worldfamous" "world" और "famous" का कन्कैटनेशन है।

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

• trie := एक नया मैप
• प्रत्येक word के लिए words में, करें
  • layer := trie
  • प्रत्येक w के लिए word में, करें
    • यदि w, layer में नहीं है, तो
      • layer[w] := एक नया मैप
    • layer := layer[w]
  • layer["*"] := एक खाली टुपल
  • एक फ़ंक्शन dfs() परिभाषित करें। यह word, num_concatenated_words लेगा
  • layer := trie
  • प्रत्येक इंडेक्स i और शब्द w के लिए word में, करें
    • यदि "*", layer में है, तो
      • यदि dfs(word[i से अंत तक], num_concatenated_words + 1) सत्य है, तो
        • सत्य लौटाएं
      • यदि w, layer में नहीं है, तो
        • असत्य लौटाएं
    • layer := layer[w]
  • यदि "*", layer में है और num_concatenated_words >= 1, तो
    • सत्य लौटाएं
  • असत्य लौटाएं
  • मुख्य विधि से निम्न करें:
  • count := 0
  • प्रत्येक word के लिए 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