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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个字符串列表 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 (" **a** cca")，下标为 1 ("b **b** bb")，下标为 3 ("cac **a** ")
"aba" -> 下标为 0 (" **a** cca")，下标为 2 ("bb **b** b")，下标为 3 ("cac **a** ")
"aba" -> 下标为 0 (" **a** cca")，下标为 1 ("b **b** bb")，下标为 3 ("acc **a** ")
"aba" -> 下标为 0 (" **a** cca")，下标为 2 ("bb **b** b")，下标为 3 ("acc **a** ")
"aba" -> 下标为 1 ("c **a** ca")，下标为 2 ("bb **b** b")，下标为 3 ("acc **a** ")
"aba" -> 下标为 1 ("c **a** ca")，下标为 2 ("bb **b** b")，下标为 3 ("cac **a** ")

示例 2：

**输入：** words = ["abba","baab"], target = "bab"
**输出：** 4
**解释：** 总共有 4 种不同形成 target 的方法。
"bab" -> 下标为 0 (" **b** aab")，下标为 1 ("b **a** ab")，下标为 2 ("ab **b** a")
"bab" -> 下标为 0 (" **b** aab")，下标为 1 ("b **a** ab")，下标为 3 ("baa **b** ")
"bab" -> 下标为 0 (" **b** aab")，下标为 2 ("ba **a** b")，下标为 3 ("baa **b** ")
"bab" -> 下标为 1 ("a **b** ba")，下标为 2 ("ba **a** b")，下标为 3 ("baa **b** ")

示例 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 都仅包含小写英文字母。

由于 words 中所有单词的长度均等于 N，因此能够维护一个计数数组 cnt，其中 cnt[i][ch] 表示在所有单词的第 i 个字符中，字符 ch 出现的次数。

记 words}[i..] 为 {x[i..] ~~ | x \in \textit{words}\。意思是：将 words 的每个单词从第 i 个字符起截取，得到的「新字典」。

随后记 dp[i][j] 为：以 words}[i..] 为字典，构造字符串 target}[j..] 的方案数。

现在，考虑如何构造字符串 target}[j..] 的首个字符，有以下两种情况：

  • 不使用字典中位置为 i 的字符。此时，问题归结于使用 words}[i+1..] 为字典构造字符串的情形，故相应的方案数为 dp[i+1][j]。
  • 使用字典中位置为 i 的字符。此时，整个字典中，共有 cnt[i][\textit{target}[j]] 个单词可供选择。在选择其中任意一个单词之后，根据题意，我们不能再选择任何一个单词的第 i 个字符或其之前的字符。因此，此后为了得到后面的字符串 target}[j+1..]，会有 dp[i+1][j+1] 种方案。

根据加法原理与乘法原理，总的方案数目为：

dp[i][j] = dp[i+1][j] + dp[i+1][j+1] \cdot cnt[i][\textit{target}[j]]

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    const int mod = 1e9+7;
    long dfs(vector<vector<long>>& dp, vector<vector<int>>& cnt, string& target, int i, int j, int n, int m) {
        if (j == m) return 1;
        if (n - i < m - j) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        
        long val = cnt[i][target[j] - 'a'] * dfs(dp, cnt, target, i + 1, j + 1, n, m);
        val += dfs(dp, cnt, target, i + 1, j, n, m);
        val %= mod;
        return dp[i][j] = val;;
    }
    
    
    int numWays(vector<string>& words, string target) {
        int n = words[0].length();
        vector<vector<int>> cnt(n, vector<int>(26, 0));
        for (const auto& s: words) {
            for (int i = 0; i < n; i++) {
                cnt[i][s[i]-'a']++;
            }
        }
        
        int m = target.length();
        vector<vector<long>> dp(n, vector<long>(m, -1));
        return dfs(dp, cnt, target, 0, 0, n, m);
    }
};

时间复杂度为 O(MN)。

 Comments
On this page
1639-通过给定词典构造目标字符串的方案数