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 的方案数。由于答案可能会很大，请对 10⁹ + 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 都仅包含小写英文字母。

解题思路#

用 \(\text{count}\) 记录 \(\text{words}\) 每列中各个字符出现的次数。

如对于测例：

1 2	`words = ["acca", "bbbb", "caca"] target = "aba"`

\(\text{count}\) 为：

\[ \begin{array}{c|cccc} &a&c&c&a\\ &b&b&b&b\\ &c&a&c&a\\ \hline a&1&1&0&2 \\ b&1&1&1&1\\ c&1&1&2&0 \end{array} \]

然后对于 \(\text{target}\) 中的每个字符，到达该位置时的方案数，等于上一个字符到达该列位置之前的方案数之和，乘以该字符在该列出现的次数。

\[ \begin{array}{c|cccc} &a&c&c&a\\ &b&b&b&b\\ &c&a&c&a\\ \hline &0&1&2&3\\ \hline a&1&1&& \\ b&&1\times(1)=1&1\times(1+1)=2&\\ a&&&0\times(1)=0&2\times{1+2}=6 \end{array} \]

然后将最后一行在 \([\text{len_target}-1,\text{len_word}-1]\) 范围内的所有数求和即可。

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        len_target, len_word = len(target), len(words[0])

        # 将 words 中的字符串排成一列
        # 保存每个字符在 words 中各列中出现的次数
        count = [[0] * len_word for _ in range(26)]
        for col_idx, col in enumerate(zip(*words)):
            for char in col:
                count[ord(char) - 97][col_idx] += 1

        # target 中第一个字符在 words 各列中出现的次数
        dp = count[ord(target[0]) - 97].copy()
        MOD = 10 ** 9 + 7
        for row_idx, char in enumerate(target[1:], 1):
            prev = dp.copy()
            for col_idx in range(row_idx, row_idx + len_word - len_target + 1):
                dp[col_idx] = (
                    sum(prev[row_idx - 1 : col_idx])
                    * count[ord(target[row_idx]) - 97][col_idx]
                ) % MOD
        return sum(dp[len_target - 1 :]) % MOD

测试数据

solution = Solution()

words = ["acca", "bbbb", "caca"]
target = "aba"
assert solution.numWays(words, target) == 6

words = ["abba", "baab"]
target = "bab"
assert solution.numWays(words, target) == 4

words = ["abcd"]
target = "abcd"
assert solution.numWays(words, target) == 1

words = ["abab", "baba", "abba", "baab"]
target = "abba"
assert solution.numWays(words, target) == 16

print("PASS!")

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

问题描述#

解题思路#

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