Python程式：給定字典，查詢形成目標字串的方法數

假設我們有一個字串列表，稱為 words，其中所有元素都具有相同的長度。我們還有一個字串，稱為 target。我們必須根據以下規則使用給定的 words 生成 target：

  • 我們應該從左到右生成 target。

  • 要獲取 target 的第 i 個字元（從 0 開始索引），當 target[i] 與 words[j][k] 相同時，我們可以選擇 words 中第 j 個字串的第 k 個字元。

  • 一旦我們使用 words 中第 j 個字串的第 k 個字元，我們就不能再使用 words 中任何字串的第 x 個字元，其中 x <= k。

  • 重複這些過程，直到我們形成整個目標字串。

因此，我們必須找到從 words 獲取 target 的方法數。答案可能非常大，因此返回答案模 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")

為了解決這個問題，我們將遵循以下步驟：

  • m := words 的數量，

  • n := target 的大小

  • d := 一個大小為 m 的列表，填充了 m 個不同的空對映

  • 對於 words 中的每個 w，執行

    • 對於 w 中的每個索引 j 和單詞 c，執行

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

  • 定義一個函式 dfs()。這將接收 i、j

  • 如果 i 等於 n，則

    • 返回 1

  • 如果 i 等於 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"

輸出

4

更新於: 2021年10月7日

702 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告