在 Python 中给定字典查找形成目标字符串的多种方法的程序
假设我们有一个名为words的字符串列表，其中所有元素的长度都相同。我们还有一个名为target的字符串。我们必须根据以下规则使用给定的单词生成目标-
我们应该从左到右生成目标。
为了得到target的第i个字符(0-indexed)，当target[i]与words[j][k]相同时，我们可以选择words中第j个字符串的第k个字符。
一旦我们使用了第j个单词串的第k个字符，我们就不能在x<=k的单词中使用任何字符串的第x个字符。
重复这些过程，直到我们形成整个目标字符串。
所以我们必须找到从单词中获取目标的方法的数量。答案可能非常大，所以返回模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")
示例
让我们看下面的实现来更好地理解
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