# 1639. 通过给定词典构造目标字符串的方案数

### 题目地址(1639. 通过给定词典构造目标字符串的方案数)

<https://leetcode.cn/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/>

### 题目描述

```
给你一个字符串列表 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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1639.number-of-ways-to-form-a-target-string-given-a-dictionary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.