Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm một số cách để tạo một chuỗi mục tiêu cho một từ điển bằng Python

Giả sử chúng ta có một danh sách các chuỗi được gọi là các từ, trong đó tất cả các phần tử có cùng độ dài. Chúng tôi cũng có một chuỗi được gọi là đích. Chúng tôi phải tạo mục tiêu bằng cách sử dụng các từ đã cho theo các quy tắc sau -

  • Chúng ta nên tạo mục tiêu từ trái sang phải.

  • Để lấy ký tự thứ i (được lập chỉ mục 0) của target, chúng ta có thể chọn ký tự thứ k của chuỗi thứ j trong các từ khi target [i] giống với các từ [j] [k].

  • Khi chúng ta sử dụng ký tự thứ k của chuỗi từ thứ j, chúng ta không thể sử dụng ký tự thứ x của bất kỳ chuỗi nào trong các từ có x <=k.

  • Lặp lại quá trình này cho đến khi chúng tôi tạo thành toàn bộ chuỗi mục tiêu.

Vì vậy, chúng ta phải tìm ra số lượng cách để có được mục tiêu từ các từ. Câu trả lời có thể rất lớn, vì vậy hãy trả về câu trả lời modulo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là words =["pqqp", "qppq"], target ="qpq", thì đầu ra sẽ là 4 vì

  • "qpq" -> tại chỉ mục 0 ("qppq"), tại chỉ mục 1 ("qppq"), tại chỉ mục 2 ("pqqp")

  • "qpq" -> tại chỉ mục 0 ("qppq"), tại chỉ mục 1 ("qppq"), tại chỉ mục 3 ("qppq")

  • "qpq" -> tại chỉ mục 0 ("qppq"), tại chỉ mục 2 ("qppq"), tại chỉ mục 3 ("qppq")

  • "qpq" -> tại chỉ mục 1 ("pqqp"), tại chỉ mục 2 ("qppq"), tại chỉ mục 3 ("qppq")

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • m:=số từ,

  • n:=kích thước của mục tiêu

  • d:=một danh sách kích thước m, chứa đầy m bản đồ trống khác nhau

  • đối với mỗi w trong từ, hãy thực hiện

    • đối với mỗi chỉ mục j và từ c trong w, thực hiện

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

  • Định nghĩa một hàm dfs (). Điều này sẽ mất tôi, j

  • nếu tôi giống n, thì

    • trả lại 1

  • nếu tôi giống với m, thì

    • trả về 0

  • return (dfs (i, j + 1) + dfs (i + 1, j + 1) * d [j, target [i]]) mod (10 ^ 9 + 7)

  • Từ phương thức chính trả về dfs ​​(0, 0)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn 

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))

Đầu vào 

"95643", "45963"

Đầu ra 

4