1639-通过给定词典构造目标字符串的方案数(Number of Ways to Form a Target String Given a Dictionary)

原文链接: https://leetcode-cn.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary

英文原文

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 i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].
Once you use the k^th character of the j^th string of words, you can no longer use the x^th 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 form target from words. Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

Example 3:

Input: words = ["abcd"], target = "abcd"
Output: 1

Example 4:

Input: words = ["abab","baba","abba","baab"], target = "abba"
Output: 16

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

通过代码

高赞题解

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

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

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

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

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

统计信息

通过次数	提交次数	AC比率
1347	3375	39.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途