पायथन में दिए गए डिक्शनरी से टारगेट स्ट्रिंग बनाने के तरीकों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास words नामक स्ट्रिंग की सूची है, जहां सभी एलिमेंट समान लंबाई के हैं। हमारे पास target नामक एक स्ट्रिंग भी है। हमें दिए गए शब्दों का उपयोग करके टारगेट जनरेट करना है निम्नलिखित नियमों के तहत:

• हमें टारगेट को बाएं से दाएं जनरेट करना चाहिए।
• टारगेट के i-वें कैरेक्टर (0-इंडेक्स्ड) को प्राप्त करने के लिए, हम words में j-वें स्ट्रिंग के k-वें कैरेक्टर का चयन कर सकते हैं जब target[i] == words[j][k]।
• एक बार जब हम words में j-वें स्ट्रिंग के k-वें कैरेक्टर का उपयोग करते हैं, तो हम words में किसी भी स्ट्रिंग के x-वें कैरेक्टर का उपयोग नहीं कर सकते जहां x <= k।
• पूरे टारगेट स्ट्रिंग को बनाने तक इस प्रक्रिया को दोहराएं।

तो हमें words से टारगेट प्राप्त करने के तरीकों की संख्या ढूंढनी है। उत्तर बहुत बड़ा हो सकता है, इसलिए उत्तर को 10^9 + 7 मॉड्यूलो वापस करें।

उदाहरण के लिए, यदि इनपुट words = ["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")

हल करने के चरण

1. m := words की संख्या
2. n := target का आकार
3. d := आकार m की सूची, m अलग-अलग खाली मैप से भरी
4. words में प्रत्येक w के लिए:
   • w में प्रत्येक इंडेक्स j और शब्द c के लिए:
     • d[j][c] := d[j][c] + 1
5. dfs() फ़ंक्शन परिभाषित करें। यह i, j लेगा:
   • यदि i == n, तो 1 वापस करें।
   • यदि j == m, तो 0 वापस करें।
   • (dfs(i, j+1) + dfs(i+1, j+1) * d[j][target[i]]) % (10^9 + 7) वापस करें।
6. मुख्य मेथड से 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"

आउटपुट

4