在 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