Skip to content

Latest commit

 

History

History
200 lines (134 loc) · 6.89 KB

1639.number-of-ways-to-form-a-target-string-given-a-dictionary.md

File metadata and controls

200 lines (134 loc) · 6.89 KB

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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