Hard

题目描述

给你一个由数字 ‘1’ 到 ‘9’ 组成的字符串 s 和两个整数 k 和 minLength。

如果 s 的一个分割满足以下条件，则称其为 美丽分割：

  • s 被分割成 k 个不重叠的子字符串。
  • 每个子字符串的长度至少为 minLength。
  • 每个子字符串以质数数字开头，以非质数数字结尾。质数数字为 ‘2’、‘3’、‘5’ 和 ‘7’，其余数字为非质数。

返回 s 的美丽分割数目。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

子字符串是字符串中连续的字符序列。

示例 1：

输入：s = "23542185131", k = 3, minLength = 2
输出：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’ 组成。

解题思路

这道题需要将字符串分割成 k 个子串，每个子串都必须满足美丽分割的条件。

核心思路分析：

  1. 美丽子串条件识别：首先需要判断一个子串是否美丽，即以质数开头（2,3,5,7）且以非质数结尾（1,4,6,8,9）。

  2. 动态规划状态设计：定义 dp[i][j] 表示前 i 个字符分割成 j 个美丽子串的方案数。

  3. 状态转移：对于每个位置 i 和分割数 j，枚举上一个分割点 prev，检查从 prev 到 i-1 的子串是否为美丽子串，如果是则累加 dp[prev][j-1] 的方案数。

优化思路：

由于需要频繁检查子串是否美丽，可以预处理所有可能的美丽子串起始和结束位置，避免重复计算。另外，由于约束条件，第一个子串必须从位置0开始且以质数开头，最后一个子串必须以非质数结尾。

边界条件处理：

  • 如果字符串首字符不是质数或末字符不是非质数，直接返回0
  • 如果字符串长度小于 k * minLength，也直接返回0

时间复杂度为 O(n^3 * k)，空间复杂度为 O(n * k)，其中 n 为字符串长度。

代码实现

class Solution {
public:
    int beautifulPartitions(string s, int k, int minLength) {
        int n = s.length();
        const int MOD = 1e9 + 7;
        
        auto isPrime = [](char c) {
            return c == '2' || c == '3' || c == '5' || c == '7';
        };
        
        // 检查字符串是否可能形成美丽分割
        if (!isPrime(s[0]) || isPrime(s[n-1]) || n < k * minLength) {
            return 0;
        }
        
        // 预处理：标记每个位置是否可以作为美丽子串的结束位置
        vector<bool> canEnd(n, false);
        for (int i = minLength - 1; i < n; i++) {
            if (!isPrime(s[i])) {
                canEnd[i] = true;
            }
        }
        
        // dp[i][j] 表示前i个字符分割成j个美丽子串的方案数
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= min(i / minLength, k); j++) {
                dp[i][j] = dp[i-1][j]; // 不在位置i-1结束分割
                
                if (j > 0 && canEnd[i-1]) {
                    // 在位置i-1结束一个分割
                    for (int prev = (j-1) * minLength; prev <= i - minLength; prev++) {
                        if (prev == 0 || (canEnd[prev-1] && isPrime(s[prev]))) {
                            dp[i][j] = (dp[i][j] + dp[prev][j-1]) % MOD;
                        }
                    }
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        n = len(s)
        MOD = 10**9 + 7
        
        def is_prime(c):
            return c in '2357'
        
        # 检查字符串是否可能形成美丽分割
        if not is_prime(s[0]) or is_prime(s[-1]) or n < k * minLength:
            return 0
        
        # 预处理：标记每个位置是否可以作为美丽子串的结束位置
        can_end = [False] * n
        for i in range(minLength - 1, n):
            if not is_prime(s[i]):
                can_end[i] = True
        
        # dp[i][j] 表示前i个字符分割成j个美丽子串的方案数
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            for j in range(min(i // minLength, k) + 1):
                dp[i][j] = dp[i-1][j]  # 不在位置i-1结束分割
                
                if j > 0 and can_end[i-1]:
                    # 在位置i-1结束一个分割
                    for prev in range((j-1) * minLength, i - minLength + 1):
                        if prev == 0 or (can_end[prev-1] and is_prime(s[prev])):
                            dp[i][j] = (dp[i][j] + dp[prev][j-1]) % MOD
        
        return dp[n][k]

public class Solution {
    public int BeautifulPartitions(string s, int k, int minLength) {
        int n = s.Length;
        const int MOD = 1000000007;
        
        bool IsPrime(char c) {
            return c == '2' || c == '3' || c == '5' || c == '7';
        }
        
        // 检查字符串是否可能形成美丽分割
        if (!IsPrime(s[0]) || IsPrime(s[n-1]) || n < k * minLength) {
            return 0;
        }
        
        // 预处理：标记每个位置是否可以作为美丽子串的结束位置
        bool[] canEnd = new bool[n];
        for (int i = minLength - 1; i < n; i++) {
            if (!IsPrime(s[i])) {
                canEnd[i] = true;
            }
        }
        
        // dp[i][j] 表示前i个字符分割成j个美丽子串的方案数
        long[,] dp = new long[n + 1, k + 1];
        dp[0, 0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= Math.Min(i / minLength, k); j++) {
                dp[i, j] = dp[i-1, j]; // 不在位置i-1结束分割
                
                if (j > 0 && canEnd[i-1]) {
                    // 在位置i-1结束一个分割
                    for (int prev = (j-1) * minLength; prev <= i - minLength; prev++) {
                        if (prev == 0 || (canEnd[prev-1] && IsPrime(s[prev]))) {
                            dp[i, j] = (dp[i, j] + dp[prev, j-1]) % MOD;
                        }
                    }
                }
            }
        }
        
        return (int)dp[n, k];
    }
}

var beautifulPartitions = function(s, k, minLength) {
    const MOD = 1000000007;
    const n = s.length;
    const isPrime = (c) => '2357'.includes(c);
    const isNonPrime = (c) => '14689'.includes(c);
    
    if (k * minLength > n || !isPrime(s[0]) || !isNonPrime(s[n-1])) {
        return 0;
    }
    
    const dp = Array(k + 1).fill().map(() => Array(n + 1).fill(0));
    dp[0][0] = 1;
    
    for (let i = 1; i <= k; i++) {
        for (let j = i * minLength; j <= n; j++) {
            for (let prev = (i - 1) * minLength; prev <= j - minLength; prev++) {
                if (dp[i-1][prev] === 0) continue;
                
                if (prev === 0 || (isNonPrime(s[prev-1]) && isPrime(s[prev]))) {
                    if (j === n || isNonPrime(s[j-1])) {
                        dp[i][j] = (dp[i][j] + dp[i-1][prev]) % MOD;
                    }
                }
            }
        }
    }
    
    return dp[k][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析结果
时间复杂度O(n² × k)
空间复杂度O(n × k)

其中 n 是字符串长度，k 是分割数目。时间复杂度主要来自三重循环：外层遍历位置，中层遍历分割数，内层遍历前一个分割点。空间复杂度来自二维DP数组的存储。

相关题目