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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告