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

🔴   🔖  数组 字符串 动态规划  🔗 力扣 LeetCode

题目

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

• target should be formed from left to right.
• To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].
• Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
• Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return the number of ways to formtarget from words. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"

Output: 6

Explanation: There are 6 ways to form target.

"aba" -> index 0 ("a cca"), index 1 ("b b bb"), index 3 ("cac a ")

"aba" -> index 0 ("a cca"), index 2 ("bb b b"), index 3 ("cac a ")

"aba" -> index 0 ("a cca"), index 1 ("b b bb"), index 3 ("acc a ")

"aba" -> index 0 ("a cca"), index 2 ("bb b b"), index 3 ("acc a ")

"aba" -> index 1 ("c a ca"), index 2 ("bb b b"), index 3 ("acc a ")

"aba" -> index 1 ("c a ca"), index 2 ("bb b b"), index 3 ("cac a ")

Example 2:

Input: words = ["abba","baab"], target = "bab"

Output: 4

Explanation: There are 4 ways to form target.

"bab" -> index 0 ("b aab"), index 1 ("b a ab"), index 2 ("ab b a")

"bab" -> index 0 ("b aab"), index 1 ("b a ab"), index 3 ("baa b ")

"bab" -> index 0 ("b aab"), index 2 ("ba a b"), index 3 ("baa b ")

"bab" -> index 1 ("a b ba"), index 2 ("ba a b"), index 3 ("baa b ")

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• All strings in words have the same length.
• 1 <= target.length <= 1000
• words[i] and target contain only lowercase English letters.

题目大意

给你一个字符串列表 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^9 + 7 取余 后返回。

（译者注：此题目求的是有多少个不同的 k 序列，详情请见示例。）

示例 1：

输入： words = ["acca","bbbb","caca"], target = "aba"

输出： 6

解释： 总共有 6 种方法构造目标串。

"aba" -> 下标为 0 ("a cca")，下标为 1 ("bb bb")，下标为 3 ("caca ")

"aba" -> 下标为 0 ("a cca")，下标为 2 ("bbb b")，下标为 3 ("caca ")

"aba" -> 下标为 0 ("a cca")，下标为 1 ("bb bb")，下标为 3 ("acca ")

"aba" -> 下标为 0 ("a cca")，下标为 2 ("bbb b")，下标为 3 ("acca ")

"aba" -> 下标为 1 ("ca ca")，下标为 2 ("bbb b")，下标为 3 ("acca ")

"aba" -> 下标为 1 ("ca ca")，下标为 2 ("bbb b")，下标为 3 ("caca ")

示例 2：

输入： words = ["abba","baab"], target = "bab"

输出： 4

解释： 总共有 4 种不同形成 target 的方法。

"bab" -> 下标为 0 ("b aab")，下标为 1 ("ba ab")，下标为 2 ("abb a")

"bab" -> 下标为 0 ("b aab")，下标为 1 ("ba ab")，下标为 3 ("baab ")

"bab" -> 下标为 0 ("b aab")，下标为 2 ("baa b")，下标为 3 ("baab ")

"bab" -> 下标为 1 ("ab ba")，下标为 2 ("baa b")，下标为 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[j] 表示构造 target 的前 j 个字符的方法总数。
• 遍历 words 的列，从右向左更新 dp 数组，计算每列对 target 各个位置的贡献。
• 通过预处理统计 words 各列每个字符的出现次数，加速计算。

1. 统计频率

• 遍历 words，统计每列每个字符的出现次数，存储为一个频率矩阵 freq。

2. 初始化 DP 数组

• 初始化 dp 数组：
  • dp[j] 表示构造 target[:j] 的方法数。
  • 初始化：dp[0] = 1，表示构造空字符串的方式数为 1。

3. 逐列更新 DP

• 对每列进行处理，从右向左更新 dp 数组：
  • 如果当前列能够为目标字符串的第 j 个字符提供一个字符：
    • 更新 dp[j] += dp[j - 1] * freq[col][target[j - 1]]。
  • 使用模 10^9 + 7 防止溢出。

4. 返回结果

• 最终 dp[target.length] 即为所求。

复杂度分析

• 时间复杂度：

  • 统计频率：O(m * w)，其中 m 是 words 的列数，w 是行数。
  • 动态规划更新：O(m * n)，其中 n 是 target 的长度。
  • 总时间复杂度：O(m * (w + n))。

• 空间复杂度：

  • 频率数组 freq：O(26 * m)。
  • 动态规划数组 dp：O(n)。
  • 总空间复杂度：O(26 * m + n)。

代码

/**
 * @param {string[]} words
 * @param {string} target
 * @return {number}
 */
var numWays = function (words, target) {
	const MOD = 1e9 + 7;
	const m = words[0].length; // 列数
	const n = target.length;

	// 统计每列字符频率
	let freq = Array.from({ length: m }, () => Array(26).fill(0));
	for (let word of words) {
		for (let col = 0; col < m; col++) {
			freq[col][word.charCodeAt(col) - 'a'.charCodeAt(0)]++;
		}
	}

	// 初始化 dp 数组
	let dp = Array(n + 1).fill(0);
	dp[0] = 1;

	// 遍历列，从右向左更新 dp 数组
	for (let col = 0; col < m; col++) {
		for (let j = n; j >= 1; j--) {
			const charIndex = target.charCodeAt(j - 1) - 'a'.charCodeAt(0);
			dp[j] += dp[j - 1] * freq[col][charIndex];
			dp[j] %= MOD;
		}
	}

	return dp[n];
};