পাইথনে শব্দ তালিকা থেকে কনক্যাটেনেটেড শব্দের সংখ্যা গণনা করার প্রোগ্রাম

একটি শব্দের তালিকা দেওয়া আছে। তালিকার শব্দগুলোকে কনক্যাটেনেট করে (ব্যবহার করতে পারে একাধিকবার) তালিকার বাকি শব্দ বানানো যায় কতগুলো তা বের করুন।

উদাহরণ: words = ["hello","world","helloworld","famous","worldfamous","programming"] → আউটপুট ২ ("helloworld" এবং "worldfamous")।

সমাধানের ধাপগুলো:

ট্রাই (Trie) বানান।
প্রতিটি শব্দের জন্য DFS দিয়ে চেক করুন যেটি একাধিক শব্দের কনক্যাটেনেশন থেকে বने।
গণনা করুন।

উদাহরণ

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"]