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]

• 将匹配和不匹配的方案数累加记为答案。

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) 完成也是极好的。

对于转移：

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), 所以可以用哈希表加速。

因此如果我们知道对于一个位置的某个字符有多少个，是不是就可以直接累加了。

这样我们的思路就是将所有位置的所有字符映射到哈希表中。

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:

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)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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