完美分割的方案数
难度:
标签:
题目描述
You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.
A partition of s is called beautiful if:
sis partitioned intoknon-intersecting substrings.- Each substring has a length of at least
minLength. - Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are
'2','3','5', and'7', and the rest of the digits are non-prime.
Return the number of beautiful partitions of s. Since the answer may be very large, return it modulo 109 + 7.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "23542185131", k = 3, minLength = 2 Output: 3 Explanation: There exists three ways to create a beautiful partition: "2354 | 218 | 5131" "2354 | 21851 | 31" "2354218 | 51 | 31"
Example 2:
Input: s = "23542185131", k = 3, minLength = 3 Output: 1 Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".
Example 3:
Input: s = "3312958", k = 3, minLength = 1 Output: 1 Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".
Constraints:
1 <= k, minLength <= s.length <= 1000sconsists of the digits'1'to'9'.
代码结果
运行时间: 250 ms, 内存: 16.2 MB
/*
题目思路：
1. 和上面的思路相同，只是这里我们使用 Java Stream 来实现。
2. 使用 stream 来处理字符串和动态规划数组。
*/
import java.util.*;
import java.util.stream.IntStream;
public class PerfectPartitionStream {
private static final int MOD = 1000000007;
private static final Set<Character> PRIME_DIGITS = new HashSet<>(Arrays.asList('2', '3', '5', '7'));
private static final Set<Character> NON_PRIME_DIGITS = new HashSet<>(Arrays.asList('1', '4', '6', '8', '9'));
public int perfectPartition(String s, int k, int minLength) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
IntStream.rangeClosed(1, n).forEach(i -> {
IntStream.rangeClosed(i - minLength, 0).filter(j -> i - j <= minLength * k && j >= 0)
.forEach(j -> {
if (PRIME_DIGITS.contains(s.charAt(j)) && NON_PRIME_DIGITS.contains(s.charAt(i - 1))) {
dp[i] = (dp[i] + dp[j]) % MOD;
}
});
});
return dp[n];
}
public static void main(String[] args) {
PerfectPartitionStream solution = new PerfectPartitionStream();
System.out.println(solution.perfectPartition("23542185131", 3, 2)); // 3
System.out.println(solution.perfectPartition("23542185131", 3, 3)); // 1
System.out.println(solution.perfectPartition("3312958", 3, 1)); // 1
}
}
解释
方法:
本题目的解法使用了动态规划。首先，创建一个布尔数组`pri`来标记哪些数字是质数。接着，将字符串`s`转换为整数数组方便处理。然后，创建一个`split_allowed`数组用来标记在哪些位置可以进行分割，即前一个字符是非质数并且后一个字符是质数的位置。接下来，使用一个动态规划数组`dp`，其中`dp[j]`表示从字符串开始到位置`j`的完美分割数。`sum_last`数组用来存储累加和，以便在计算中快速获取区间和。对于每段可能的分割，更新`dp`和`sum_cur`数组，并最终返回最后的分割方案数。
时间复杂度:
O(kn)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在检查是否可以作为分割点时，只考虑前一个字符是非质数和后一个字符是质数的情况？是否还需要考虑字符长度的限制？
▷🦆
在处理字符串首尾字符不符合条件的情况时，为什么直接返回0？是否有可能存在其他有效的分割方法？
▷🦆
在动态规划实现中，`dp[j]`是如何确保每个子字符串长度至少为`minLength`？
▷🦆
在更新`sum_cur`数组时，为什么选择累加`dp[j]`值而不是直接使用`dp[j]`的当前值？
▷