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

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

हमें बाएं से दाएं लक्ष्य उत्पन्न करना चाहिए।
लक्ष्य का ith वर्ण (0-अनुक्रमित) प्राप्त करने के लिए, हम jth स्ट्रिंग के kth वर्ण को शब्दों में चुन सकते हैं जब लक्ष्य [i] शब्द [j] [k] के समान हो।
एक बार जब हम शब्दों के jth स्ट्रिंग के kth वर्ण का उपयोग करते हैं, तो हम किसी भी स्ट्रिंग के xth वर्ण का उपयोग उन शब्दों में नहीं कर सकते हैं जहाँ x <=k.
इस प्रक्रिया को तब तक दोहराएं जब तक हम संपूर्ण लक्ष्य स्ट्रिंग नहीं बना लेते।

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

इसलिए, यदि इनपुट शब्द =["pqqp", "qppq"], लक्ष्य ="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") पर

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

मी :=शब्दों की संख्या,
n :=लक्ष्य का आकार
d :=आकार m की एक सूची, m अलग-अलग खाली मानचित्रों से भरी हुई है
शब्दों में प्रत्येक w के लिए, करें
- w में प्रत्येक अनुक्रमणिका j और शब्द c के लिए करें
  - d[j, c] :=d[j, c] + 1
फ़ंक्शन को परिभाषित करें dfs() । यह मैं, जम्मू ले जाएगा
अगर मैं n के समान हूं, तो
- वापसी 1
अगर मैं एम के समान हूं, तो
- वापसी 0
वापसी (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))

इनपुट

"95643", "45963"