1639. 通过给定词典构造目标字符串的方案数 - Kotlin 二维DP+前缀和优化 双百
Problem: 1639. 通过给定词典构造目标字符串的方案数
[TOC]
初始思路
将整个words抽象成一个char类型的矩阵，则题干可以理解为：有一个初始指向第0列列指针chrIndex，我们每次可以进行两种操作中的一种：
- 将列指针向前移动1位（注意列指针无法后退）
- 从列指针指向的列（即遍历
word in words中的word[chrIndex]）选中一个字符与target的当前字符匹配后向前移动1位
设dp[targetIndex][chrIndex]为target[targetIndex]匹配列指针chrIndex指向列的所有可能性
考虑到后效性，我们应当先从target的targetIndex由小到大遍历，即从target[0]逐步构建至target[target.length-1]
令列指针遍历words矩阵的列宽，即words[0].length（由于words中各单词长度相同，这里的words[0]可以是任意words中的单词），随后遍历列指针chrIndex指向列中的所有所有字符，即行指针wordIndex遍历words.length，如果有字符words[wordIndex][chrIndex]匹配target[targetIndex]，则说明chrIndex指向的列匹配到了target[targetIndex]，由于chrIndex无法后退，那么target[0..targetIndex-1]的部分就只能从 0至chrIndex-1 中匹配
对于0..chrIndex-1中的任意一种情况，只要能够匹配到targetIndex-1就能转移到当前的状态上，那么就应当加上该种情况的方案数，此时有
对于边界情况，即targetIndex==0的情况，当前状态能够匹配target中的第一个字符，对于words中任意一个当前列能匹配字符的单词都有一种方案，即
复杂度
- 时间复杂度: ,其中T为target长度，M为words中单词数量，N为单词长度
- 空间复杂度:
当然，这个复杂度是过不了的，会卡在大概第80/90个样例左右
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
fun numWays(words: Array<String>, target: String): Int {
val dp = Array(target.length) { LongArray(words[0].length) { 0 } }
for ((index, chrTarget) in target.withIndex()) {
for (chrIndex in words[0].indices) {
for (word in words) {
if (word[chrIndex] == chrTarget) {
if (index == 0) {
dp[index][chrIndex]++
} else if (chrIndex > 0) {
for (i in 0 until chrIndex) {
dp[index][chrIndex] = (dp[index][chrIndex] + dp[index - 1][i]) % 1000000007
}
}
}
}
}
}
return (dp[target.length - 1].sum() % 1000000007).toInt()
}
}
|
前缀和优化
观察初始版本的代码可以发现，主要问题在于当chrIndex能够匹配到targetIndex时，我们需要将当前情况的方案数加上在0到chrIndex之间的所有能够匹配到targetIndex-1的所有方案数，导致多了一层循环
由于我们每次都是先计算匹配到targetIndex-1的情况再去计算targetIndex的情况，因此可以通过一个前缀和数组进行优化，在遍历targetIndex时，presum[chrIndex]记录列指针chrIndex之前的所有列能够匹配到targetIndex-1的所有情况之和，那么上述的递推公式就简化为
在每次计算完targetIndex的情况后，再去更新前缀和数组即可
复杂度
- 时间复杂度: ,其中T为target长度，M为words中单词数量，N为单词长度
- 空间复杂度:
遗憾的是，这样子仍然会卡在第85/90或者86/90左右的样例上，需要进一步优化
Code
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
fun numWays(words: Array<String>, target: String): Int {
val dp = Array(target.length) { LongArray(words[0].length) { 0 } }
val presum = LongArray(words[0].length) { 0 }
for ((index, chrTarget) in target.withIndex()) {
for (chrIndex in words[0].indices) {
for (word in words) {
if (word[chrIndex] == chrTarget) {
if (index == 0) {
dp[index][chrIndex]++
} else if (chrIndex > 0) {
dp[index][chrIndex] = (dp[index][chrIndex] + presum[chrIndex - 1]) % 1000000007
}
}
}
}
for (chrIndex in words[0].indices) {
presum[chrIndex] = (if (chrIndex != 0) presum[chrIndex - 1] else 0) + dp[index][chrIndex]
}
}
return (dp[target.length - 1].sum() % 1000000007).toInt()
}
}
|
优化遍历
考虑从循环条件上优化，考虑两种情况：
第一种情况：当chrIndex过小时，举例来说，我们无法从矩阵中第1个字符匹配到target中的第5个字符，因为我们需要先匹配target中的前4个字符，因此chrIndex应当从targetIndex而非0开始遍历
第二种情况：当chrIndex过大时，举例来说，如果chrIndex已经遍历到最后一列，而target中还需要继续匹配5个字符，这种情况也是不成立的，因此chrIndex应当从words[0].length - (target.length - index)而非words[0].length结束遍历
复杂度
- 时间复杂度: ,其中T为target长度，M为words中单词数量，N为单词长度
- 空间复杂度:
Code
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
fun numWays(words: Array<String>, target: String): Int {
val dp = Array(target.length) { LongArray(words[0].length) { 0 } }
val presum = LongArray(words[0].length) { 0 }
for ((index, chrTarget) in target.withIndex()) {
for (chrIndex in index..words[0].length - (target.length - index)) {
for (word in words) {
if (word[chrIndex] == chrTarget) {
if (index == 0) {
dp[index][chrIndex]++
} else if (chrIndex > 0) {
dp[index][chrIndex] = (dp[index][chrIndex] + presum[chrIndex - 1]) % 1000000007
}
}
}
}
for (chrIndex in index .. words[0].length - (target.length - index)) {
presum[chrIndex] = (if (chrIndex != index) presum[chrIndex - 1] else 0) + dp[index][chrIndex]
}
}
return (dp[target.length - 1].sum() % 1000000007).toInt()
}
}
|
