作者推荐
本文涉及知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
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 的方案数。由于答案可能会很大，请对 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 都仅包含小写英文字母。
动态规划
动态规划的状态表示
vCan[i][j] 如果包括x，words有几个元素的下标j 是’a’+i。
pre[j] 表示words[?][0,j)和target[0,i)匹配。dp[j]表示 words[?][0,j)和target[0,i+1)匹配。
动态规划的转移方程
dp[j] = ∑ k = 0 j \Large\sum_{k=0}^{j}∑k=0jpre[k]
vCan[i]必须包括j。
动态规划的初始值
pre[0]=1，其它全为0。
动态规划的填表顺序
i从小到大，j从小到大。
动态规划的返回值
pre的和。
代码
核心代码
template<int MOD = 1000000007> class C1097Int { public: C1097Int(long long llData = 0) :m_iData(llData% MOD) { } C1097Int operator+(const C1097Int& o)const { return C1097Int(((long long)m_iData + o.m_iData) % MOD); } C1097Int& operator+=(const C1097Int& o) { m_iData = ((long long)m_iData + o.m_iData) % MOD; return *this; } C1097Int& operator-=(const C1097Int& o) { m_iData = (m_iData + MOD - o.m_iData) % MOD; return *this; } C1097Int operator-(const C1097Int& o) { return C1097Int((m_iData + MOD - o.m_iData) % MOD); } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int& operator*=(const C1097Int& o) { m_iData = ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator<(const C1097Int& o)const { return m_iData < o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet = 1, iCur = *this; while (n) { if (n & 1) { iRet *= iCur; } iCur *= iCur; n >>= 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData = 0;; }; class Solution { public: int numWays(vector<string>& words, string target) { m_c = words[0].size(); vector<vector<int>> vCan(26,vector<int>(m_c)); for (int i = 0; i < m_c; i++) { for (int j = 0; j < words.size(); j++) { const int index = words[j][i] - 'a'; vCan[index][i]++; } } vector<C1097Int<>> pre(m_c + 1); pre[0] = 1; for (int i = 0; i < target.size(); i++) { vector<C1097Int<>> dp(m_c + 1); C1097Int<> biSum = 0; int k = 0; for (int j = 0 ; j < m_c ; j++ ) { while (k <= j) { biSum += pre[k++]; } dp[j+1] = biSum*vCan[target[i]-'a'][j]; } pre.swap(dp); } return std::accumulate(pre.begin(), pre.end(), C1097Int<>()).ToInt(); } int m_c; };
核心代码
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<string> words; string target; { Solution sln; words = { "acca", "bbbb", "caca" }, target = "aba"; auto res = sln.numWays(words, target); Assert(res, 6); } { Solution sln; words = { "abba", "baab" }, target = "bab"; auto res = sln.numWays(words, target); Assert(res, 4); } { Solution sln; words = { "abcd" }, target = "abcd"; auto res = sln.numWays(words, target); Assert(res, 1); } { Solution sln; words = { "abab", "baba", "abba", "baab" }, target = "abba"; auto res = sln.numWays(words, target); Assert(res, 16); } }
2023年2月
class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{
} C1097Int operator+(const C1097Int& o)const { return C1097Int((m_iData + o.m_iData) % s_iMod); } C1097Int& operator+=(const C1097Int& o) { m_iData = (m_iData + o.m_iData) % s_iMod; return *this; } C1097Int operator*(const C1097Int& o)const { return((long long)m_iData *o.m_iData) % s_iMod; } C1097Int& operator*=(const C1097Int& o) { m_iData =((long long)m_iData *o.m_iData) % s_iMod; return *this; } int ToInt()const { return m_iData; }
private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}
class Solution {
public:
int numWays(vector& words, string target) {
m_r = words.size();
m_c = words[0].size();
m_vCharNums.assign(m_c, vector(26));
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
m_vCharNums[c][words[r][c] - ‘a’]++;
}
}
// 已经处理完的target串 对应words[?]的前pre[i]个字符
vector pre(m_c + 1);
pre[0] = 1;
for (const auto& ch : target)
{
vector dp(m_c + 1);
C1097Int iSub = 0;
for (int j = 1; j <= m_c; j++)
{
iSub += pre[j - 1];
dp[j] = iSub * m_vCharNums[j - 1][ch - ‘a’];
}
pre.swap(dp);
}
return std::accumulate(pre.begin(), pre.end(), C1097Int(0)).ToInt();
}
int m_r;
int m_c;
vector<vector> m_vCharNums;
};
