完美分割的方案数

标签: 字符串 动态规划

难度: Hard

给你一个字符串 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' 之一。

Submission

运行时间: 250 ms

内存: 16.2 MB

MOD = int(1e9 + 7)

class Solution:

    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        n = len(s)
        pri = [False] * 11
        pri[2] = pri[3] = pri[5] = pri[7] = True
        s = [int(i) for i in s]
        if pri[s[-1]] is True or pri[s[0]] is False:
            return 0
        split_allowed = [True] * n
        for i in range(n - 1):
            if not (pri[s[i]] == False and pri[s[i + 1]] == True):
                split_allowed[i] = False
        #print(split_allowed)
        # dp = [0 if ind < minLength else int(i) for ind, val in enumerate(split_allowed)]
        dp_last = dp = [0] * (n + 1)
        for i in range(1,len(dp_last)):
            dp_last[i] = split_allowed[i-1]


        sum_last = [1] * (n + 1)

        for i in range(1, k + 1):
            # es = []
            sum_cur = [0] * (n + 1)
            dp = [0] * (n+1)
            #print('\t', sum_last)
            for j in range(i * minLength, n + 1):
                if not split_allowed[j - 1]:
                    sum_cur[j] = sum_cur[j - 1]
                    continue
                # f = bisect.bisect_left(es, j - minLength) - 1
                # if f == -1:
                #     dp[j] = sum_last[j - minLength - 1]
                # else:
                #     dp[j] = sum_last[es[f]]
                dp[j] = sum_last[j - minLength]
                sum_cur[j] = (sum_cur[j - 1] + dp[j]) % MOD
                # if dp[j] != 0:
                #     es.append(j)

            #print(dp)
            dp_last = dp
            sum_last = sum_cur

        return dp[-1]

Explain

本题目的解法使用了动态规划。首先，创建一个布尔数组`pri`来标记哪些数字是质数。接着，将字符串`s`转换为整数数组方便处理。然后，创建一个`split_allowed`数组用来标记在哪些位置可以进行分割，即前一个字符是非质数并且后一个字符是质数的位置。接下来，使用一个动态规划数组`dp`，其中`dp[j]`表示从字符串开始到位置`j`的完美分割数。`sum_last`数组用来存储累加和，以便在计算中快速获取区间和。对于每段可能的分割，更新`dp`和`sum_cur`数组，并最终返回最后的分割方案数。

时间复杂度: O(kn)

空间复杂度: O(n)

MOD = int(1e9 + 7)

class Solution:

    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        n = len(s)
        pri = [False] * 11
        pri[2] = pri[3] = pri[5] = pri[7] = True  # 标记质数
        s = [int(i) for i in s]  # 将字符转换为整数
        if pri[s[-1]] is True or pri[s[0]] is False:
            return 0  # 处理字符串首尾字符不符合条件的情况
        split_allowed = [True] * n
        for i in range(n - 1):
            if not (pri[s[i]] == False and pri[s[i + 1]] == True):
                split_allowed[i] = False  # 标记可以分割的位置

        dp_last = dp = [0] * (n + 1)  # 初始化dp数组
        for i in range(1,len(dp_last)):
            dp_last[i] = split_allowed[i-1]  # 初始化dp_last为分割允许的情况

        sum_last = [1] * (n + 1)  # 初始化sum_last数组

        for i in range(1, k + 1):
            sum_cur = [0] * (n + 1)
            dp = [0] * (n+1)
            for j in range(i * minLength, n + 1):
                if not split_allowed[j - 1]:
                    sum_cur[j] = sum_cur[j - 1]  # 更新当前累加和数组
                    continue
                dp[j] = sum_last[j - minLength]  # 计算当前dp值
                sum_cur[j] = (sum_cur[j - 1] + dp[j]) % MOD  # 更新累加和取模

            dp_last = dp
            sum_last = sum_cur

        return dp[-1]  # 返回结果

Explore

在此问题中，分割点的选择基于特定的质数规则，即前一个字符（分割点前的字符）必须是非质数，后一个字符（分割点后的字符）必须是质数。这种规则是为了确保每个分割出来的子字符串在特定的质数条件下开始和结束。至于字符长度的限制，这确实是一个重要的考虑因素，但在确定分割点是否允许时，长度限制并未直接涉及。字符长度的限制在动态规划的具体实现中考虑，通过控制从哪些位置可以开始新的子段，以确保每个子段至少有 `minLength` 长度。

如果字符串的首字符是质数或尾字符是非质数，则整个字符串无法在题目定义的规则下完美分割，因为所有的分割都必须确保每个子字符串从非质数开始到质数结束。由于首尾字符设置了整个字符串的起始和结束条件，如果这些条件不满足，那么无法形成任何有效的分割，因此直接返回0是合理的。在这种情况下，不存在其他有效的分割方法。

在动态规划的实现中，`dp[j]`表示从字符串开始到位置`j`的完美分割数。为了确保每个子字符串长度至少为`minLength`，代码中的循环从`i * minLength`开始，这保证了每次计算`dp[j]`时，都至少从`minLength`长度之前的索引开始考虑，即确保了分割出来的每个子字符串长度至少为`minLength`。此外，计算`dp[j]`时，使用的是`sum_last[j - minLength]`，这也进一步确保了长度限制的遵守。

在更新`sum_cur`数组时，选择累加`dp[j]`值是为了维护一个到当前位置为止的所有可能的分割方案的总和。这样做可以便于下一次计算新的`dp[j]`值时，直接利用这个累积和，无需重新遍历之前的元素来求和。这是一种优化手段，使得每次更新`dp[j]`时的计算更加高效，只需要O(1)的时间即可得到所需的前缀和。