class Solution {
public:
int numberOfCombinations(string num) {
}
};
1977. 划分数字的方案数
你写下了若干 正整数 ，并将它们连接成了一个字符串 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' 。原站题解
cpp 解法, 执行用时: 268 ms, 内存消耗: 121 MB, 提交时间: 2023-07-12 09:22:40
/**
* 动态规划
**/
class Solution {
private:
static constexpr int mod = 1000000007;
public:
int numberOfCombinations(string num) {
if (num[0] == '0') {
return 0;
}
int n = num.size();
// 预处理 lcp
vector<vector<int>> lcp(n, vector<int>(n));
for (int i = n - 1; i >= 0; --i) {
lcp[i][n - 1] = (num[i] == num[n - 1]);
for (int j = i + 1; j < n - 1; ++j) {
lcp[i][j] = (num[i] == num[j] ? lcp[i + 1][j + 1] + 1 : 0);
}
}
// 辅助函数，计算 x = (x + y) % mod
auto update = [&](int& x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
};
// 动态规划
vector<vector<int>> f(n, vector<int>(n));
// 边界 f[0][..] = 1
for (int i = 0; i < n; ++i) {
f[0][i] = 1;
}
for (int i = 1; i < n; ++i) {
// 有前导零，无需转移
if (num[i] == '0') {
continue;
}
// 前缀和
int presum = 0;
for (int j = i; j < n; ++j) {
int length = j - i + 1;
f[i][j] = presum;
if (i - length >= 0) {
// 使用 lcp 比较 num(2i-j-1,i-1) 与 num(i,j) 的大小关系
if (lcp[i - length][i] >= length || num[i - length + lcp[i - length][i]] < num[i + lcp[i - length][i]]) {
update(f[i][j], f[i - length][i - 1]);
}
// 更新前缀和
update(presum, f[i - length][i - 1]);
}
}
}
// 最终答案即为所有 f[..][n-1] 的和
int ans = 0;
for (int i = 0; i < n; ++i) {
update(ans, f[i][n - 1]);
}
return ans;
}
};
python3 解法, 执行用时: 3272 ms, 内存消耗: 551 MB, 提交时间: 2023-07-12 09:21:07
'''
'''
class Solution:
def numberOfCombinations(self, num: str) -> int:
mod = 10**9 + 7
if num[0] == "0":
return 0
n = len(num)
# 预处理 lcp
# lcp[i][j] 表示在字符串 num 中，以 i 开始的后缀与以 j 开始的后缀的「最长公共前缀」的长度
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[i][j] 表示对于字符串 num 的第 0,1,⋯,j 个字符进行划分，并且最后一个数使用了第
# i,i+1,⋯j 个字符的方案数。为了叙述方便，用num(i,j) 表示该数。
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
golang 解法, 执行用时: 132 ms, 内存消耗: 161 MB, 提交时间: 2023-07-12 09:17:36
const mod int = 1e9 + 7
func numberOfCombinations(s string) (ans int) {
if s[0] == '0' {
return
}
n := len(s)
// lcp[i][j] 后缀s[i:] 和 后缀 s[j:] 的最长公共前缀的长度
lcp := make([][]int, n+1)
for i := range lcp {
lcp[i] = make([]int, n+1)
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if s[i] == s[j] {
lcp[i][j] = lcp[i+1][j+1] + 1
}
}
}
// 返回 s[l1:l2] <= s[l2:r2]
lessEq := func(l1, l2, r2 int) bool {
l := lcp[l1][l2]
return l >= r2-l2 || s[l1+l] < s[l2+l]
}
// f[i][j] s的前j个字符串划分出的最后一个整数的起始位置为i时的方案数
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
for j := 0; j < n; j++ {
f[0][j] = 1
}
for i := 1; i < n; i++ {
if s[i] == '0' {
continue
}
// k 和 j 同时向左向右扩展
for j, k, sum := i, i-1, 0; j < n; j++ {
f[i][j] = sum // 对应上面所说的长度小于最后一个划分出的整数
if k < 0 {
continue
}
if s[k] > '0' && lessEq(k, i, j+1) {
f[i][j] = (f[i][j] + f[k][i-1]) % mod // 对应上面所说的长度等于最后一个划分出的整数
}
sum = (sum + f[k][i-1]) % mod
k--
}
}
for _, row := range f {
ans = (ans + row[n-1]) % mod
}
return
}