难度: Hard
你写下了若干 正整数 ，并将它们连接成了一个字符串 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' 。运行时间: 2113 ms
内存: 538.0 MB
class Solution:
def numberOfCombinations(self, num: str) -> int:
mod = 10**9 + 7
if num[0] == "0":
return 0
n = len(num)
# 预处理 lcp
lcp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
lcp[i][n - 1] = int(num[i] == num[n - 1])
for j in range(i + 1, n - 1):
lcp[i][j] = (lcp[i + 1][j + 1] + 1 if num[i] == num[j] else 0)
# 动态规划
f = [[0] * n for _ in range(n)]
# 边界 f[0][..] = 1
for i in range(n):
f[0][i] = 1
for i in range(1, n):
# 有前导零，无需转移
if num[i] == "0":
continue
# 前缀和
presum = 0
for j in range(i, n):
length = j - i + 1
f[i][j] = presum % mod
if i - length >= 0:
# 使用 lcp 比较 num(2i-j-1,i-1) 与 num(i,j) 的大小关系
if lcp[i - length][i] >= length or num[i - length + lcp[i - length][i]] < num[i + lcp[i - length][i]]:
f[i][j] = (f[i][j] + f[i - length][i - 1]) % mod
# 更新前缀和
presum += f[i - length][i - 1]
# 最终答案即为所有 f[..][n-1] 的和
ans = sum(f[i][n - 1] for i in range(n)) % mod
return ans
此题使用动态规划的方法。首先进行特殊情况的判断：如果字符串的第一个字符为'0'，由于不能有前导0，直接返回0。定义dp数组f[i][j]，表示考虑num的子串num[0..j]，且最后一个数字为num[i..j]时的方案数。初始化f[0][i]=1，即当第一个数字扩展到i时，只有一种划分方案。对于每个位置i到j，若num[i]=='0'，则跳过，因为不能有前导0。为了保证非递减，需要比较当前数字与前一个数字的大小。这通过预处理一个最长公共前缀数组lcp来辅助，减少比较次数。动态规划递推时，若当前数字大于等于前一个数字，则累加前面的方案数。最后，将所有以n-1结尾的方案数相加，得到总方案数。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def numberOfCombinations(self, num: str) -> int:
mod = 10**9 + 7
# 特殊情况处理，如果首字符为0，则无有效方案
if num[0] == '0':
return 0
n = len(num)
# 预处理最长公共前缀数组lcp
lcp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
lcp[i][n - 1] = int(num[i] == num[n - 1])
for j in range(i + 1, n - 1):
lcp[i][j] = (lcp[i + 1][j + 1] + 1 if num[i] == num[j] else 0)
# 初始化动态规划数组
f = [[0] * n for _ in range(n)]
for i in range(n):
f[0][i] = 1
for i in range(1, n):
if num[i] == '0':
continue
presum = 0
for j in range(i, n):
length = j - i + 1
f[i][j] = presum % mod
if i - length >= 0:
# 判断当前数字是否大于等于前一个数字
if lcp[i - length][i] >= length or num[i - length + lcp[i - length][i]] < num[i + lcp[i - length][i]]:
f[i][j] = (f[i][j] + f[i - length][i - 1]) % mod
presum += f[i - length][i - 1] if i - length >= 0 else 0
# 计算最终的方案数
ans = sum(f[i][n - 1] for i in range(n)) % mod
return ans
动态规划数组f[i][j]表示考虑数字字符串num的子串num[0..j]，且最后一个数字为num[i..j]时的方案数。这意味着，f[i][j]计算的是所有以num[i..j]结尾的划分方案的数量。初始化f[0][i]=1是因为当只考虑从头开始到i位置的子串时，整个子串作为一个数字是唯一的划分方式，因此初始方案数为1。
最长公共前缀数组lcp[i][j]表示字符串num中从位置i开始和从位置j开始的子串的最长公共前缀的长度。计算lcp数组是通过动态规划完成的，从字符串的末尾向前计算，确保lcp[i][j]正确反映两个位置的子串前缀匹配的长度。在算法中，lcp数组用于快速判断两个子串的大小关系，这有助于减少重复的字符串比较，提高算法效率。
在数字字符串的划分中，任何部分如果以'0'开头且长度大于1，则这样的划分是不合法的（例如'012'或'00123'）。因此，在动态规划过程中，如果某个位置i的字符为'0'，则跳过这一步是因为以i开始的任何长度大于1的划分都是无效的，从而保证所有划分都是合法的数字。
在计算dp值时，需要确保新形成的数字（子串num[i..j]）与前一个数字（子串num[i-length..i-1]）的大小关系符合非递减顺序。比较`lcp[i - length][i]`与`length`是为了快速判断这两个子串的大小关系。如果最长公共前缀长度小于子串长度，则可以直接通过公共前缀后的第一个不同字符判断两个子串的大小；如果等于或大于，表示这两个子串相等，满足非递减条件。这种比较方法避免了完整的字符串比较，提高了效率。