# 1639. 通过给定词典构造目标字符串的方案数
### 题目地址(1639. 通过给定词典构造目标字符串的方案数)
### 题目描述
```
给你一个字符串列表 words 和一个目标字符串 target 。words 中所有字符串都 长度相同 。
你的目标是使用给定的 words 字符串列表按照下述规则构造 target ：
从左到右依次构造 target 的每一个字符。
为了得到 target 第 i 个字符（下标从 0 开始），当 target[i] = words[j][k] 时，你可以使用 words 列表中第 j 个字符串的第 k 个字符。
一旦你使用了 words 中第 j 个字符串的第 k 个字符，你不能再使用 words 字符串列表中任意单词的第 x 个字符（x <= k）。也就是说，所有单词下标小于等于 k 的字符都不能再被使用。
请你重复此过程直到得到目标字符串 target 。
请注意， 在构造目标字符串的过程中，你可以按照上述规定使用 words 列表中 同一个字符串 的 多个字符 。
请你返回使用 words 构造 target 的方案数。由于答案可能会很大，请对 109 + 7 取余 后返回。
（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）
示例 1：
输入：words = ["acca","bbbb","caca"], target = "aba"
输出：6
解释：总共有 6 种方法构造目标串。
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("caca")
"aba" -> 下标为 0 ("acca")，下标为 1 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 0 ("acca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("acca")
"aba" -> 下标为 1 ("caca")，下标为 2 ("bbbb")，下标为 3 ("caca")
示例 2：
输入：words = ["abba","baab"], target = "bab"
输出：4
解释：总共有 4 种不同形成 target 的方法。
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 2 ("abba")
"bab" -> 下标为 0 ("baab")，下标为 1 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 0 ("baab")，下标为 2 ("baab")，下标为 3 ("baab")
"bab" -> 下标为 1 ("abba")，下标为 2 ("baab")，下标为 3 ("baab")
示例 3：
输入：words = ["abcd"], target = "abcd"
输出：1
示例 4：
输入：words = ["abab","baba","abba","baab"], target = "abba"
输出：16
提示：
1 <= words.length <= 1000
1 <= words[i].length <= 1000
words 中所有单词长度相同。
1 <= target.length <= 1000
words[i] 和 target 都仅包含小写英文字母。
```
### 前置知识
* 哈希表
* 动态规划
### 公司
* 暂无
### 思路
定义 dp(col, pos) 表示从 col 列**开始**匹配 target\[:pos+1] 的方案数。那么答案就是 dp(0, 0)
> target\[:pos+1] 表示从索引 0 到索引 pos 的 target 切片
接下来我们考虑如何转移：
* 对于每一个 col， 我们可以选择匹配或者不匹配。
* 如果匹配， 那么需要满足 word\[col] == target\[pos]
* 将匹配和不匹配的方案数累加记为答案。
```py
class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 10 ** 9 + 7
k = len(words[0])
cnt = [[0] * k for _ in range(26)]
for j in range(k):
for word in words:
cnt[ord(word[j]) - ord('a')][j] += 1
@cache
def dp(col, pos):
if len(target) - pos > len(words[0]) - col: return 0 # 剪枝
if pos == len(target): return 1
if col == len(words[0]): return 0
ans = dp(col+1, pos) # skip
for word in words: # pick one of the word[col]
if word[col] == target[pos]:
ans += dp(col+1, pos+1)
ans %= MOD
return ans % MOD
return dp(0, 0) % MOD
```
另外 m 为 words 长度， k 为 word 长度， n 为 target 长度。
那么复杂度为保底的 DP 复杂度 n \* k，再乘以 dp 内部转移的复杂度为 m，因此复杂度为 $O(m \* n \* k)$，代入题目的数据范围， 可以达到 10 \*\* 9， 无法通过。
> 大于 10 \*\* 7 一般都无法通过，具体可以参考我的插件中的复杂度速查表。
这里的 dp 维度无法优化（注意到有的题目维度可以优化， 这样 dp 的打底复杂度也可以进一步降低）。我们考虑优化转移， 如果转移可以 O(1) 完成也是极好的。
对于转移：
```py
for word in words: # pick one of the word[col]
if word[col] == target[pos]:
ans += dp(col+1, pos+1)
ans %= MOD
```
不难看出这其实就是找有多少满足这个 if 条件的， 就在 ans 上累加多少个 dp(col+1, pos+1), 所以可以用哈希表加速。
因此如果我们知道对于一个位置的某个字符有多少个，是不是就可以直接累加了。
这样我们的思路就是将所有位置的所有字符映射到哈希表中。
```py
cnt = [[0] * k for _ in range(26)]
for j in range(k):
for word in words:
cnt[ord(word[j]) - ord('a')][j] += 1
```
时间复杂度降低到 $O(n \* k)$，代入到题目是 10 \*\* 6 ，常数项又不大，因此可以通过。
### 关键点
* 使用哈希表加速 dp 状态转移
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 10 ** 9 + 7
k = len(words[0])
cnt = [[0] * k for _ in range(26)]
for j in range(k):
for word in words:
cnt[ord(word[j]) - ord('a')][j] += 1
@cache
def dp(col, pos):
if len(target) - pos > len(words[0]) - col: return 0 # 剪枝
if pos == len(target): return 1
if col == len(words[0]): return 0
ans = dp(col+1, pos) # skip
ans += dp(col+1, pos+1) * cnt[ord(target[pos]) - ord('a')][col] # 根据上面的提示，我们可以这样优化
return ans % MOD
return dp(0, 0) % MOD
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n \* k)$
* 空间复杂度：$O(n \* k)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
