2026-10-06：统计从两个字符串形成目标字符串的不同方案数。用go语言，给定两个字符串 word1、word2，以及一个目标字符串 target。现在需要从 word1 和 word2 中挑选字符，按顺序组成 target。
要求如下：
target 中的每一个字符，都必须由 word1 或 word2 中某个相同的字符来提供。
如果在组成 target 时，某个字符取自 word1，那么所有取自 word1 的字符在原字符串中的位置必须依次向后，不能相同，也不能倒退。
如果在组成 target 时，某个字符取自 word2，那么所有取自 word2 的字符在原字符串中的位置也必须依次向后，不能相同，也不能倒退。
最终不能只使用其中一个字符串，word1 和 word2 都必须至少贡献一个字符。
两种选择方案是否不同，取决于 target 的每一个位置到底选了哪个字符串，以及选的是该字符串中的哪一个下标。只要有一个位置对应的来源字符串不同，或者下标不同，就算不同方案。
求所有满足条件的方案数量。由于结果可能很大，最后需要对 10 的 9 次方加 7 取余，并返回取余后的结果。
1 <= word1.length, word2.length, target.length <= 100。
word1、word2 和 target 仅由小写英文字母组成。
输入： word1 = “abc”, word2 = “bac”, target = “abc”。
输出： 5。
解释：
有 5 种形成 target 的方案：
word1[0] = ‘a’, word1[1] = ‘b’, word2[2] = ‘c’
word1[0] = ‘a’, word2[0] = ‘b’, word1[2] = ‘c’
word1[0] = ‘a’, word2[0] = ‘b’, word2[2] = ‘c’
word2[1] = ‘a’, word1[1] = ‘b’, word1[2] = ‘c’
word2[1] = ‘a’, word1[1] = ‘b’, word2[2] = ‘c’
所有方案都保持了每个字符串内部递增的下标顺序，并且从每个字符串中至少选择了一个字符。
题目来自力扣3981。#=
大体步骤如下：
1. 明确状态含义
定义三个维度来表示动态规划的状态：
- 第一个维度
i：表示当前已经匹配到目标字符串target的前i个字符。 - 第二个维度
j：表示当前允许使用word1的前j - 1个字符，也就是下标从0到j - 2的字符。j的取值范围是1到m1 + 1，其中m1是word1的长度。 - 第三个维度
k：表示当前允许使用word2的前k - 1个字符，也就是下标从0到k - 2的字符。k的取值范围是1到m2 + 1，其中m2是word2的长度。
因此，状态f[i][j][k]表示：在只允许使用word1的前j - 1个字符和word2的前k - 1个字符的条件下，能够形成target前i个字符的方案总数。
2. 初始化空目标字符串的情况
当i = 0时，target为空字符串，不需要选择任何字符。只要允许使用的字符范围不是完全为空（即j >= 1且k >= 1），就都有一种方案：什么都不选。
所以，对于所有j从1到m1 + 1，k从1到m2 + 1，都令f[0][j][k] = 1。
3. 逐字符处理目标字符串
外层循环依次处理target的每一个字符。假设当前处理的是target的第i个字符（从0开始计数），字符为ch。
接下来要计算f[i + 1][j + 1][k + 1]，即匹配了前i + 1个目标字符，并且允许使用word1前j个字符（下标0到j - 1）和word2前k个字符（下标0到k - 1）的方案数。
这里j从0遍历到m1，k从某个下界开始遍历到m2。下界是max(0, i + 1 - j)，因为总共可用的字符数是j + k，要匹配i + 1个目标字符，必须满足j + k >= i + 1。
4. 利用二维前缀和进行容斥
计算f[i + 1][j + 1][k + 1]时，先考虑不依赖新加入的word1第j个字符和word2第k个字符的情况。这可以通过二维前缀和的容斥得到：
f[i + 1][j][k + 1]：允许word1前j - 1个字符，word2前k个字符。f[i + 1][j + 1][k]：允许word1前j个字符，word2前k - 1个字符。f[i + 1][j][k]：允许word1前j - 1个字符，word2前k - 1个字符。
基础方案数为：
f[i + 1][j][k + 1] + f[i + 1][j + 1][k] - f[i + 1][j][k]
这部分涵盖了所有不使用新字符来匹配当前目标字符的方案。
5. 加上使用word1新字符匹配当前目标字符的方案
如果当前目标字符ch等于word1中下标为j - 1的字符（前提是j > 0），那么可以用这个字符来匹配ch。此时，之前匹配target前i个字符时，必须恰好使用了word2中下标为k - 1的字符。这种方案数等于：
f[i][j][k + 1] - f[i][j][k]
解释：f[i][j][k + 1]允许word1前j - 1个字符，word2前k个字符；f[i][j][k]允许word1前j - 1个字符，word2前k - 1个字符。两者之差正好是必须使用word2第k个字符的方案数。这样加上后，就补全了所有使用word1第j个字符匹配当前字符的方案。
6. 加上使用word2新字符匹配当前目标字符的方案
类似地，如果当前目标字符ch等于word2中下标为k - 1的字符（前提是k > 0），则可以用这个字符匹配ch。此时，之前匹配target前i个字符时，必须恰好使用了word1中下标为j - 1的字符。这种方案数等于：
f[i][j + 1][k] - f[i][j][k]
解释：f[i][j + 1][k]允许word1前j个字符，word2前k - 1个字符；f[i][j][k]允许word1前j - 1个字符，word2前k - 1个字符。两者之差正好是必须使用word1第j个字符的方案数。加上后，就补全了所有使用word2第k个字符匹配当前字符的方案。
7. 取模并完成状态转移
将上述所有部分相加，得到f[i + 1][j + 1][k + 1]的原始值，然后对10^9 + 7取模，保证结果在整数范围内。
8. 计算最终答案
当所有目标字符处理完毕后，f[n][m1 + 1][m2 + 1]表示使用word1全部字符和word2全部字符时，形成整个target的方案总数。但这个总数包含了只使用word1或只使用word2的情况。
题目要求两个字符串都必须至少贡献一个字符，所以需要排除：
- 只使用
word1的方案：对应word2允许使用前0个字符，即k = 1，所以是f[n][m1 + 1][1]。 - 只使用
word2的方案：对应word1允许使用前0个字符，即j = 1，所以是f[n][1][m2 + 1]。
因此最终答案：
ans = f[n][m1 + 1][m2 + 1] - f[n][m1 + 1][1] - f[n][1][m2 + 1]
由于取模可能导致负数，最后再对10^9 + 7取模并调整到非负范围。
复杂度分析
时间复杂度：
外层循环遍历target的每个字符，共n次；中层循环遍历word1的允许前缀长度，共m1 + 1次；内层循环遍历word2的允许前缀长度，虽然下界是max(0, i + 1 - j)，但最坏情况下接近m2次。因此总操作次数为O(n * m1 * m2)。每次操作都是常数时间的加减和取模，所以总时间复杂度为O(n * m1 * m2)。额外空间复杂度：
使用了一个三维数组f，大小为(n + 1) * (m1 + 2) * (m2 + 2)，所以额外空间为O(n * m1 * m2)。没有使用其他大规模数据结构。
由于题目中n, m1, m2都不超过100，最大状态数约为100^3 = 1,000,000，时间和空间都可以接受。
Go完整代码如下：
packagemainimport("fmt")funcinterleaveCharacters(word1,word2,targetstring)int{constmod=1_000_000_007n,m1,m2:=len(target),len(word1),len(word2)f:=make([][][]int,n+1)fori:=rangef{f[i]=make([][]int,m1+2)forj:=rangef[i]{f[i][j]=make([]int,m2+2)}}forj:=1;j<m1+2;j++{fork:=1;k<m2+2;k++{f[0][j][k]=1}}fori,ch:=rangetarget{forj:=rangem1+1{// j+k >= i+1fork:=max(0,i+1-j);k<=m2;k++{res:=f[i+1][j][k+1]+f[i+1][j+1][k]-f[i+1][j][k]ifj>0&&word1[j-1]==byte(ch){res+=f[i][j][k+1]-f[i][j][k]}ifk>0&&word2[k-1]==byte(ch){res+=f[i][j+1][k]-f[i][j][k]}f[i+1][j+1][k+1]=res%mod}}}ans:=f[n][m1+1][m2+1]-f[n][m1+1][1]-f[n][1][m2+1]return(ans%mod+mod)%mod// 保证 ans 非负}funcmain(){word1:="abc"word2:="bac"target:="abc"result:=interleaveCharacters(word1,word2,target)fmt.Println(result)}Python完整代码如下：
# -*-coding:utf-8-*-definterleave_characters(word1:str,word2:str,target:str)->int:MOD=1_000_000_007n,m1,m2=len(target),len(word1),len(word2)# f[i][j][k] 表示处理到 target 的前 i 个字符，# word1 中已用到前 j 个位置，word2 中已用到前 k 个位置的方案数f=[[[0]*(m2+2)for_inrange(m1+2)]for_inrange(n+1)]# 初始化：target 为空时，任意前缀状态都算 1 种方案forjinrange(1,m1+2):forkinrange(1,m2+2):f[0][j][k]=1fori,chinenumerate(target):forjinrange(m1+1):# k 的下界保证 j + k >= i + 1，即已选字符数足够覆盖 target 的前 i+1 个字符start_k=max(0,i+1-j)forkinrange(start_k,m2+1):res=f[i+1][j][k+1]+f[i+1][j+1][k]-f[i+1][j][k]ifj>0andword1[j-1]==ch:res+=f[i][j][k+1]-f[i][j][k]ifk>0andword2[k-1]==ch:res+=f[i][j+1][k]-f[i][j][k]f[i+1][j+1][k+1]=res%MOD ans=f[n][m1+1][m2+1]-f[n][m1+1][1]-f[n][1][m2+1]return(ans%MOD+MOD)%MODif__name__=="__main__":word1="abc"word2="bac"target="abc"result=interleave_characters(word1,word2,target)print(result)C++完整代码如下：
#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespacestd;constintMOD=1000000007;intinterleaveCharacters(string word1,string word2,string target){intn=target.size();intm1=word1.size();intm2=word2.size();// f[i][j][k] 表示处理到 target 的前 i 个字符，// word1 已用到前 j 个位置，word2 已用到前 k 个位置的方案数vector<vector<vector<int>>>f(n+1,vector<vector<int>>(m1+2,vector<int>(m2+2,0)));// 初始化：target 为空时，任意前缀状态都算 1 种方案for(intj=1;j<m1+2;++j){for(intk=1;k<m2+2;++k){f[0][j][k]=1;}}for(inti=0;i<n;++i){charch=target[i];for(intj=0;j<=m1;++j){// 保证 j + k >= i + 1intstart_k=max(0,i+1-j);for(intk=start_k;k<=m2;++k){longlongres=f[i+1][j][k+1]+f[i+1][j+1][k]-f[i+1][j][k];if(j>0&&word1[j-1]==ch){res+=f[i][j][k+1]-f[i][j][k];}if(k>0&&word2[k-1]==ch){res+=f[i][j+1][k]-f[i][j][k];}f[i+1][j+1][k+1]=res%MOD;}}}longlongans=f[n][m1+1][m2+1]-f[n][m1+1][1]-f[n][1][m2+1];return(ans%MOD+MOD)%MOD;// 保证结果非负}intmain(){string word1="abc";string word2="bac";string target="abc";intresult=interleaveCharacters(word1,word2,target);cout<<result<<endl;return0;}
