LeetCode 题解工作台
划分数字的方案数
你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。 请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 10 9 + 7 取余 后返回。 示例 1： 输…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
定义 表示字符串 `num` 的前 个字符，且最后一个数字的长度为 时的方案数。显然答案为 $\sum_{j=0}^{n} dp[n][j]$。初始值 $dp[0][0] = 1$。 对于 ，对应的上一个数的结尾应该是 ，我们可以枚举 ，其中 $k\le j$。对于 $k \lt j$ 的部分，即长度小于 的方案数可以直接加给 ，即 $dp[i][j] = \sum_{k=0}^{j-1}…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你写下了若干 正整数 ，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 非递减 的且 没有 任何数字有前导 0 。
请你返回有多少种可能的 正整数数组 可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余 后返回。
示例 1：
输入：num = "327" 输出：2 解释：以下为可能的方案： 3, 27 327
示例 2：
输入：num = "094" 输出：0 解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 3：
输入：num = "0" 输出：0 解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 4：
输入：num = "9999999999999" 输出：101
提示：
1 <= num.length <= 3500num只含有数字'0'到'9'。
解题思路
方法一：动态规划 + 前缀和
定义 表示字符串 num 的前 个字符，且最后一个数字的长度为 时的方案数。显然答案为 。初始值 。
对于 ，对应的上一个数的结尾应该是 ，我们可以枚举 ，其中 。对于 的部分，即长度小于 的方案数可以直接加给 ，即 。因为前一个数字更短，也就意味着它比当前数更小。这里可以用前缀和优化。
但是当 时，我们需要判断同样长度的两个数字的大小关系。如果前一个数字比当前数字大，那么这种情况是不合法的，我们不应该将其加给 。否则，我们可以将其加给 。这里我们可以先用 的时间预处理得到“最长公共前缀”，然后用 的时间判断两个同样长度的数字的大小关系。
时间复杂度 ，空间复杂度 。其中 为字符串 num 的长度。
class Solution:
def numberOfCombinations(self, num: str) -> int:
def cmp(i, j, k):
x = lcp[i][j]
return x >= k or num[i + x] >= num[j + x]
mod = 10**9 + 7
n = len(num)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
if num[i] == num[j]:
lcp[i][j] = 1 + lcp[i + 1][j + 1]
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
v = 0
if num[i - j] != '0':
if i - j - j >= 0 and cmp(i - j, i - j - j, j):
v = dp[i - j][j]
else:
v = dp[i - j][min(j - 1, i - j)]
dp[i][j] = (dp[i][j - 1] + v) % mod
return dp[n][n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the DP implementation. Naive DP can reach O(n^2) for both, while optimizations using suffix arrays or prefix comparisons reduce constant factors without changing the asymptotic bounds. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering how to represent previous number states efficiently?
- question_mark
Can you handle cases with leading zeros correctly?
- question_mark
Think about reducing repeated string comparisons using suffix information.
常见陷阱
外企场景- error
Not skipping numbers starting with zero leads to invalid sequences.
- error
Comparing numbers incorrectly without handling lengths can yield wrong DP transitions.
- error
Inefficient repeated substring comparisons can cause timeouts on long inputs.
进阶变体
外企场景- arrow_right_alt
Count sequences under strictly increasing integer constraints instead of non-decreasing.
- arrow_right_alt
Allow leading zeros and compute all possible sequences including them.
- arrow_right_alt
Return all valid sequences as actual lists instead of only the count.