โปรแกรมค้นหาหลายวิธีในการสร้างสตริงเป้าหมายที่กำหนดให้กับพจนานุกรมในPython

สมมติว่าเรามีรายการสตริงที่เรียกว่าคำ ซึ่งองค์ประกอบทั้งหมดมีความยาวเท่ากัน เรายังมีสตริงที่เรียกว่าเป้าหมาย เราต้องสร้างเป้าหมายโดยใช้คำที่กำหนดภายใต้กฎต่อไปนี้ -

เราควรสร้างเป้าหมายจากซ้ายไปขวา
เพื่อให้ได้อักขระ ith (ดัชนี 0 ตัว) ของเป้าหมาย เราสามารถเลือกอักขระที่ k ของสตริง jth ในคำได้เมื่อ target[i] เหมือนกับ word[j][k]
เมื่อเราใช้อักขระ kth ของสตริงคำที่ j เราจะไม่สามารถใช้อักขระ 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 และ word c ใน w ให้ทำ
  - 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, target[i]]) mod (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"