在Python中查找给定字典下形成目标字符串的方法数量的程序

假设我们有一个名为words的字符串列表，其中所有元素长度都相同。我们还有一个名为target的字符串。我们必须根据以下规则使用给定的单词生成目标字符串−

我们应该从左到右生成目标。
要获取目标的第i个字符（0索引），当target [i]与words [j] [k]相同时，我们可以选择单词中第j个字符串的第k个字符。
一旦我们使用了单词中第j个字符串的第k个字符，我们就不能使用任何单词中的xth字符，其中x <= k。
重复这个过程直到我们形成整个目标字符串。

所以我们必须找到从单词中获得目标的方法数。答案可能非常大，因此返回答案模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 :=单词数量,
n :=目标大小
d :=大小为m的列表，其中填充有m个不同的空映射
给每个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))