পাইথনে ডিকশনারি দিয়ে টার্গেট স্ট্রিং ফর্ম করার পথের সংখ্যা খুঁজে বের করার প্রোগ্রাম

আমাদের একটি স্ট্রিং লিস্ট আছে words, যেখানে সব এলিমেন্টের দৈর্ঘ্য একই। আমাদের আরও একটি স্ট্রিং আছে target। আমাদের দেওয়া words ব্যবহার করে target জেনারেট করতে হবে নিচের নিয়মগুলো মেনে:

target-কে বাম থেকে ডানে জেনারেট করতে হবে।
target-এর i-তম ক্যারেক্টার (০-ইন্ডেক্সড) পেতে, আমরা words-এর j-তম স্ট্রিংর k-তম ক্যারেক্টার সিলেক্ট করতে পারি যখন target[i] == words[j][k]।
একবার words-এর j-তম স্ট্রিংর k-তম ক্যারেক্টার ব্যবহার করলে, আমরা words-এর যেকোনো স্ট্রিংর x-তম ক্যারেক্টার ব্যবহার করতে পারব না যেখানে x <= k।
এই প্রসেসটি পূরণ될 때까지 চলবে।

আমাদের words থেকে target পাওয়ার পথের সংখ্যা বের করতে হবে। উত্তর অনেক বড় হতে পারে, তাই 10^9 + 7 দিয়ে মডুলো করে রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট words = ["pqqp","qppq"], target = "qpq" হলে আউটপুট হবে 4 কারণ:

"qpq" -> ইন্ডেক্স ০ ("qppq"), ইন্ডেক্স ১ ("qppq"), ইন্ডেক্স ২ ("pqqp")
"qpq" -> ইন্ডেক্স ০ ("qppq"), ইন্ডেক্স ১ ("qppq"), ইন্ডেক্স ৩ ("qppq")
"qpq" -> ইন্ডেক্স ০ ("qppq"), ইন্ডেক্স ২ ("qppq"), ইন্ডেক্স ৩ ("qppq")
"qpq" -> ইন্ডেক্স ১ ("pqqp"), ইন্ডেক্স ২ ("qppq"), ইন্ডেক্স ৩ ("qppq")

সমাধানের ধাপসমূহ (DP + মেমোইজেশন)

m := words[0]-এর দৈর্ঘ্য, n := target-এর দৈর্ঘ্য
d := m আকারের লিস্ট, m টি আলাদা খালি ম্যাপ দিয়ে ফিল করে
words-এর প্রতিটি w এর জন্য:
- w-এর প্রতিটি ইন্ডেক্স j এবং ক্যারেক্টার c এর জন্য:
  - d[j][c] += 1
dfs(i, j) ফাংশন ডিফাইন করুন:
- যদি i == n হয়, তবে ১ রিটার্ন করুন
- যদি j == m হয়, তবে ০ রিটার্ন করুন
- (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[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))

ইনপুট

["pqqp","qppq"], "qpq"