2478-完美分割的方案数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。

如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：

  • s 被分成 k 段互不相交的子字符串。
  • 每个子字符串长度都 至少 为 minLength 。
  • 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 '2' ，'3' ，'5' 和 '7' ，剩下的都是非质数数字。

请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。

一个 子字符串 是字符串中一段连续字符串序列。

示例 1：

**输入：** s = "23542185131", k = 3, minLength = 2
**输出：** 3
**解释：** 存在 3 种完美分割方案：
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"

示例 2：

**输入：** s = "23542185131", k = 3, minLength = 3
**输出：** 1
**解释：** 存在一种完美分割方案："2354 | 218 | 5131" 。

示例 3：

**输入：** s = "3312958", k = 3, minLength = 1
**输出：** 1
**解释：** 存在一种完美分割方案："331 | 29 | 58" 。

提示：

  • 1 <= k, minLength <= s.length <= 1000
  • s 每个字符都为数字 '1' 到 '9' 之一。

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场周赛的看法~

定义 f[i][j] 表示把 s 的前 j 个字符分割成 i 段的方案数（每段需要满足题目的后两个要求）。

定义 j 为分割点，等价于 s[j] 不是质数且 s[j+1] 是质数。

如果 j 是分割点，那么可以考虑枚举第 i-1 段与第 i 段的分割点 j’，需满足 j-j’\ge \textit{minLength。

累加所有 f[i-1][j’]，记作 sum，那么 f[i][j]=\textit{sum。

每个 f[i][j] 都要这样累加就太慢了，需要优化。

我们可以从小到大同时遍历 j’ 和 j，一边更新 sum，一边计算 f[i][j]，具体见代码。

为方便计算，定义初始值 f[0][0] = 1，表示空串的 0 个分割算作一种方案。因为这个原因，要把所有下标 j 向后移动一位。

答案为 f[k][n]，这里 n 为 s 的长度。

还有一些剪枝和循环次数优化的小技巧，具体见代码。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def beautifulPartitions(self, s: str, k: int, l: int) -> int:
        MOD = 10 ** 9 + 7
        def is_prime(c: str) -> bool:
            return c in "2357"
        # 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
        def can_partition(j: int) -> bool:
            return j == 0 or j == n or not is_prime(s[j - 1]) and is_prime(s[j])

        n = len(s)
        if k * l > n or not is_prime(s[0]) or is_prime(s[-1]):  # 剪枝
            return 0
        f = [[0] * (n + 1) for _ in range(k + 1)]
        f[0][0] = 1
        for i in range(1, k + 1):
            sum = 0
            # 优化：枚举的起点和终点需要给前后的子串预留出足够的长度
            for j in range(i * l, n - (k - i) * l + 1):
                if can_partition(j - l): sum = (sum + f[i - 1][j - l]) % MOD  # j'=j-l 双指针
                if can_partition(j): f[i][j] = sum
        return f[k][n]
[sol1-Java]
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
class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int beautifulPartitions(String S, int k, int l) {
        var s = S.toCharArray();
        var n = s.length;
        if (k * l > n || !isPrime(s[0]) || isPrime(s[n - 1])) // 剪枝
            return 0;
        var f = new int[k + 1][n + 1];
        f[0][0] = 1;
        for (var i = 1; i <= k; ++i) {
            var sum = 0;
            // 优化：枚举的起点和终点需要给前后的子串预留出足够的长度
            for (var j = i * l; j + (k - i) * l <= n; j++) {
                if (canPartition(s, j - l)) sum = (sum + f[i - 1][j - l]) % MOD; // j'=j-l 双指针
                if (canPartition(s, j)) f[i][j] = sum;
            }
        }
        return f[k][n];
    }

    private boolean isPrime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    // 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
    private boolean canPartition(char[] s, int j) {
        return j == 0 || j == s.length || !isPrime(s[j - 1]) && isPrime(s[j]);
    }
}
[sol1-C++]
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
class Solution {
    const int MOD = 1e9 + 7;

    bool is_prime(char c) {
        return c == '2' || c == '3' || c == '5' || c == '7';
    }

    // 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
    bool can_partition(string &s, int j) {
        return j == 0 || j == s.length() || !is_prime(s[j - 1]) && is_prime(s[j]);
    }

public:
    int beautifulPartitions(string &s, int k, int l) {
        int n = s.length();
        if (k * l > n || !is_prime(s[0]) || is_prime(s[n - 1])) // 剪枝
            return 0;
        int f[k + 1][n + 1]; memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= k; ++i) {
            int sum = 0;
            // 优化：枚举的起点和终点需要给前后的子串预留出足够的长度
            for (int j = i * l; j + (k - i) * l <= n; j++) {
                if (can_partition(s, j - l)) sum = (sum + f[i - 1][j - l]) % MOD; // j'=j-l 双指针
                if (can_partition(s, j)) f[i][j] = sum;
            }
        }
        return f[k][n];
    }
};
[sol1-Go]
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
func beautifulPartitions(s string, k, l int) (ans int) {
	const mod int = 1e9 + 7
	isPrime := func(c byte) bool { return strings.IndexByte("2357", c) >= 0 }
	n := len(s)
	if k*l > n || !isPrime(s[0]) || isPrime(s[n-1]) { // 剪枝
		return
	}
	// 判断是否可以在 j-1 和 j 之间分割（开头和末尾也算）
	canPartition := func(j int) bool { return j == 0 || j == n || !isPrime(s[j-1]) && isPrime(s[j]) }
	f := make([][]int, k+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	f[0][0] = 1
	for i := 1; i <= k; i++ {
		sum := 0
		// 优化：枚举的起点和终点需要给前后的子串预留出足够的长度
		for j := i * l; j+(k-i)*l <= n; j++ {
			if canPartition(j - l) { // j'=j-l 双指针
				sum = (sum + f[i-1][j-l]) % mod
			}
			if canPartition(j) {
				f[i][j] = sum
			}
		}
	}
	return f[k][n]
}

复杂度分析

  • 时间复杂度：O(k(n-kl))，其中 n 为 s 的长度。
  • 空间复杂度：O(kn)。注：也可以用滚动数组优化至 O(n)。

相似题目

 Comments
On this page
2478-完美分割的方案数