LeetCode 题解工作台
完美分割的方案数
给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。 如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割： s 被分成 k 段互不相交的子字符串。 每个子字符串长度都 至少 为 minLength 。 每个子字符串的第一个字符都是一…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示前 个字符分割成 段的方案数。初始化 $f[0][0] = 1$，其余 $f[i][j] = 0$。 首先，我们需要判断第 个字符是否能成为第 段的最后一个字符，它需要同时满足以下条件：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 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 <= 1000s每个字符都为数字'1'到'9'之一。
解题思路
方法一：动态规划
我们定义 表示前 个字符分割成 段的方案数。初始化 ，其余 。
首先，我们需要判断第 个字符是否能成为第 段的最后一个字符，它需要同时满足以下条件：
- 第 个字符是一个非质数；
- 第 个字符是一个质数，或者第 个字符是整个字符串的最后一个字符。
如果第 个字符不能成为第 段的最后一个字符，那么 。否则有：
也就是说，我们要枚举上一段的结尾是哪个字符。这里我们用前缀和数组 来优化枚举的时间复杂度。
那么有：
时间复杂度 ，空间复杂度 。其中 和 分别是字符串 的长度和分割的段数。
class Solution:
def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
primes = '2357'
if s[0] not in primes or s[-1] in primes:
return 0
mod = 10**9 + 7
n = len(s)
f = [[0] * (k + 1) for _ in range(n + 1)]
g = [[0] * (k + 1) for _ in range(n + 1)]
f[0][0] = g[0][0] = 1
for i, c in enumerate(s, 1):
if i >= minLength and c not in primes and (i == n or s[i] in primes):
for j in range(1, k + 1):
f[i][j] = g[i - minLength][j - 1]
for j in range(k + 1):
g[i][j] = (g[i - 1][j] + f[i][j]) % mod
return f[n][k]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of dynamic programming with state transitions.
- question_mark
Check if the candidate suggests a greedy approach in combination with dynamic programming.
- question_mark
Evaluate if the candidate considers edge cases such as large strings and the modulo operation.
常见陷阱
外企场景- error
Failing to handle partitions with leading zeros.
- error
Overcomplicating the problem by not applying the greedy approach effectively.
- error
Ignoring the modulo operation and producing numbers too large to handle.
进阶变体
外企场景- arrow_right_alt
Consider a variation where the number of partitions k is fixed, but the minimum length minLength varies.
- arrow_right_alt
Explore a scenario where the string contains only a single digit repeated, requiring careful handling of partitions.
- arrow_right_alt
Try solving the problem with a more restrictive set of partition conditions, such as ensuring each partition forms a valid number.