考点
思路
一、问题抽象
给定一个字符串数组
words，其中每个字符串长度相同，设长度为 \(m\)。 给定目标字符串
target，长度为 \(n\)。
构造规则如下：
- 从左到右依次构造
target；
- 构造第 \(i\)
个字符时，选择某一列 \(j\)；
- 在该列中，从所有
words 的第 \(j\) 个字符里任选一个；
- 列号必须严格递增（即不能重复使用或回退列）。
要求计算构造出整个 target 的方案数，结果对 \(10^9+7\) 取模。
二、预处理：列字符计数
由于在同一列中可以从不同单词中选字符，列中字符的出现次数是方案数的乘数。
定义计数数组： \[
\text{cnt}[j][c] = \text{第 } j \text{ 列中字母 } c \text{ 的出现次数}
\] 其中：
- \(j \in [1, m]\)
- \(c \in
['a','z']\)
该数组仅与 words 有关，可一次性预处理。
三、动态规划状态定义（二维）
状态定义
定义二维 DP 数组： \[
f[i][j] = \text{使用前 } j \text{ 列，恰好构造出 } target \text{ 的前 }
i \text{ 个字符，且第 } i \text{ 个字符使用了第 } j \text{ 列的方案数}
\] 含义要点：
- \(i\) 控制已构造的字符数；
- \(j\) 控制当前字符使用的列；
- “使用了第 \(j\)
列”隐含列号严格递增的约束。
初始值
\[
f[0][0] = 1
\]
解释：
- 构造空字符串；
- 不使用任何列；
- 只有 1 种方式。
这是整个 DP 的唯一非零起点。
四、状态转移方程
前缀和优化思想
当构造第 \(i\) 个字符并使用第 \(j\) 列时：
- 上一个字符必须来自某一列 \(k <
j\)；
- 可行的前置状态是所有 \(f[i-1][1 \dots
j-1]\)。
定义前缀和： \[
S_{i-1}(j-1) = \sum_{k=0}^{j-1} f[i-1][k]
\]
转移方程
设当前要匹配的字符为 \(target[i]\)，则有： \[
f[i][j]
=
S_{i-1}(j-1)
\times
\text{cnt}[j][target[i]]
\pmod{10^9+7}
\] 含义分解：
- 从所有合法的前一列方案中转移；
- 当前列能提供多少个目标字符，就放大多少倍；
- 列号天然保证严格递增。
前缀和的递推维护
在固定 \(i\)
的情况下，从左到右扫描列： \[
S_{i-1}(j) = S_{i-1}(j-1) + f[i-1][j]
\] 这样每个状态转移为 \(O(1)\)，整体复杂度为： \[
O(n \cdot m)
\]
五、答案构成
完整构造出 target 后，第 \(n\) 个字符可能来自任意一列： \[
\text{Answer} = \sum_{j=1}^{m} f[n][j] \pmod{10^9+7}
\]
六、空间优化：滚动数组
观察转移关系可知：
- 第 \(i\) 行仅依赖第 \(i-1\) 行；
- 可将
f[i][*] 压缩为 f[i&1][*]。
关键注意点（非常重要）
- 每一轮必须清空当前行；
- 否则当某一列
cnt[j][c]=0
时，旧值会残留并污染结果。
七、AC代码
1️⃣ 二维 DP + 前缀和（原始版）
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
static const int maxn = 1e3 + 5, mod = 1e9 + 7;
int numWays(vector<string>& words, string target) {
long long f[maxn][maxn];
memset(f, 0, sizeof(f));
int cnt[maxn][26];
memset(cnt, 0, sizeof(cnt));
int m = words[0].size();
for (int j = 1; j <= m; ++j) {
for (int k = 0; k < words.size(); ++k) {
cnt[j][words[k][j - 1] - 'a']++;
}
}
int n = target.size();
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
long long s = f[i - 1][0];
for (int j = 1; j <= m; ++j) {
if (cnt[j][target[i - 1] - 'a']) {
f[i][j] = (f[i][j] + s * cnt[j][target[i - 1] - 'a']) % mod;
}
s = (s + f[i - 1][j]) % mod;
}
}
long long res = 0;
for (int j = 1; j <= m; ++j) {
res = (res + f[n][j]) % mod;
}
return (int)res;
}
};
|
2️⃣ 滚动数组优化版（空间 O(m)）
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
static const int maxn = 1e3 + 5, mod = 1e9 + 7;
int numWays(vector<string>& words, string target) {
long long f[2][maxn];
memset(f, 0, sizeof(f));
int cnt[maxn][26];
memset(cnt, 0, sizeof(cnt));
int m = words[0].size();
for (int j = 1; j <= m; ++j) {
for (int k = 0; k < words.size(); ++k) {
cnt[j][words[k][j - 1] - 'a']++;
}
}
int n = target.size();
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
int cur = i & 1;
int pre = (i - 1) & 1;
for (int j = 0; j <= m; ++j) {
f[cur][j] = 0;
}
long long s = f[pre][0];
for (int j = 1; j <= m; ++j) {
if (cnt[j][target[i - 1] - 'a']) {
f[cur][j] = s * cnt[j][target[i - 1] - 'a'] % mod;
}
s = (s + f[pre][j]) % mod;
}
}
long long res = 0;
for (int j = 1; j <= m; ++j) {
res = (res + f[n & 1][j]) % mod;
}
return (int)res;
}
};
|