পাইথনে একটি অভিধান প্রদত্ত একটি লক্ষ্য স্ট্রিং গঠনের উপায় খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে শব্দ নামক স্ট্রিং এর একটি তালিকা আছে, যেখানে সমস্ত উপাদান একই দৈর্ঘ্যের। আমরা টার্গেট নামক একটি স্ট্রিং আছে. নিম্নলিখিত নিয়মগুলির অধীনে প্রদত্ত শব্দগুলি ব্যবহার করে আমাদের লক্ষ্য তৈরি করতে হবে -

• আমাদের বাম থেকে ডানে লক্ষ্য তৈরি করা উচিত।

• লক্ষ্যের ith অক্ষর (0-সূচীযুক্ত) পেতে, আমরা শব্দে jth স্ট্রিং-এর kth অক্ষর নির্বাচন করতে পারি যখন লক্ষ্য[i] শব্দ[j][k] এর মতো হয়।

• একবার আমরা শব্দের jth স্ট্রিং এর kth অক্ষর ব্যবহার করলে, আমরা কোন স্ট্রিং এর xth অক্ষর ব্যবহার করতে পারি না যেখানে x <=k.

• আমরা সম্পূর্ণ টার্গেট স্ট্রিং তৈরি না হওয়া পর্যন্ত এই প্রক্রিয়াগুলি পুনরাবৃত্তি করুন৷

তাই শব্দ থেকে লক্ষ্য অর্জনের উপায় বের করতে হবে। উত্তরটি অনেক বড় হতে পারে, তাই উত্তর মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুট শব্দের মত হয় =["pqqp","qppq"], target ="qpq", তাহলে আউটপুট হবে 4 কারণ

• "qpq" -> সূচক 0 এ ("qppq"), সূচক 1 এ ("qppq"), সূচক 2 এ ("pqqp")

• "qpq" -> সূচক 0 এ ("qppq"), সূচক 1 এ ("qppq"), সূচক 3 এ ("qppq")

• "qpq" -> সূচক 0 এ ("qppq"), সূচক 2 এ ("qppq"), সূচক 3 এ ("qppq")

• "qpq" -> সূচক 1 এ ("pqqp"), সূচক 2 এ ("qppq"), সূচক 3 এ ("qppq")

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

• m :=শব্দের সংখ্যা,

• n :=লক্ষ্যের আকার

• d :=m আকারের একটি তালিকা, m বিভিন্ন খালি মানচিত্র দিয়ে পূর্ণ

• প্রতিটি শব্দের জন্য, করুন

  • প্রতিটি সূচকের জন্য j এবং শব্দ c w, do

    • d[j, c] :=d[j, c] + 1

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি i, j

  লাগবে

• যদি আমি n এর মত হয়, তাহলে

  • রিটার্ন 1

• যদি আমি m এর মত হয়, তাহলে

  • রিটার্ন 0

• রিটার্ন (dfs(i, j+1) + dfs(i+1, j+1) * d[j, টার্গেট[i]]) মোড (10^9 + 7)

• প্রধান পদ্ধতি থেকে dfs(0, 0)

  রিটার্ন করুন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

from collections import Counter
def solve(words, target):
   m, n = len(words[0]), len(target)
   d = [Counter() for _ in range(m)]
   for w in words:
      for j, c in enumerate(w):
         d[j][c] += 1

   def dfs(i, j):
      if i == n:
         return 1
      if j == m:
         return 0
      return (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) % int(1e9 + 7)

   return dfs(0, 0)

words = ["pqqp","qppq"]
target = "qpq"
print(solve(words, target))

ইনপুট

"95643", "45963"

আউটপুট

4