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

ধরুন আমাদের স্ট্রিং এর একটি তালিকা আছে; আমাদের তালিকায় অন্যান্য শব্দের সংযোজন শব্দের সংখ্যা খুঁজে বের করতে হবে। যেকোন সংখ্যক বার সংযুক্ত করার সময় আমরা শব্দগুলি পুনরায় ব্যবহার করতে পারি।

সুতরাং, যদি ইনপুট শব্দের মত হয় =["hello", "world", "helloworld", "famous", "worldfamous", "programming"], তাহলে আউটপুট হবে 2, কারণ "helloworld" হল "এর সংমিশ্রণ হ্যালো" এবং "বিশ্ব"। "বিশ্ববিখ্যাত" হল "বিশ্ব" এবং "বিখ্যাত" এর সংমিশ্রণ।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• trie :=একটি নতুন মানচিত্র
• শব্দে প্রতিটি শব্দের জন্য, করুন
  • স্তর :=চেষ্টা করুন
  • শব্দে প্রতিটি w এর জন্য, করুন
    • যদি w লেয়ারে না থাকে, তাহলে
      • স্তর[w] :=একটি নতুন মানচিত্র
    • স্তর :=স্তর[w]
  • স্তর["*"] :=একটি খালি টিপল
  • একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি শব্দ লাগবে, num_concatenated_words
  • স্তর :=চেষ্টা করুন
  • প্রতিটি সূচক i এবং শব্দের w শব্দের জন্য, করুন
    • যদি "*" লেয়ারে থাকে, তাহলে
      • যদি dfs(word[index 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