原文链接: https://leetcode-cn.com/problems/number-of-ways-to-separate-numbers

英文原文

You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was non-decreasing and that no integer had leading zeros.

Return the number of possible lists of integers that you could have written down to get the string num. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: num = "327"
Output: 2
Explanation: You could have written down the numbers:
3, 27
327

Example 2:

Input: num = "094"
Output: 0
Explanation: No numbers can have leading zeros and all numbers must be positive.

Example 3:

Input: num = "0"
Output: 0
Explanation: No numbers can have leading zeros and all numbers must be positive.

Example 4:

Input: num = "9999999999999"
Output: 101

 

Constraints:

• 1 <= num.length <= 3500
• num consists of digits '0' through '9'.

中文题目

你写下了若干 正整数 ，并将它们连接成了一个字符串 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 <= 3500
• num 只含有数字 '0' 到 '9' 。

通过代码

高赞题解

方法一：动态规划

本题较难。

容易想到$\mathcal{O}(N^3)$的动态规划：用$dp[i][j]$表示到第$i$个位置，最后一个数字的长度为$j$时的方案数，则其对应的上一个数的结尾应该是$i-j$，我们就可以枚举$dp[i-j][k]$，$k\le j$。其中，$k<j$的部分可以直接加上（因为前面的数字长度较短，所以一定更小），但$k=j$时，我们需要判断两个数字的大小关系。

利用前缀和的方法可以将$k<j$的部分优化到$\mathcal{O}(1)$时间，但此时整体的复杂度还是$\mathcal{O}(N^3)$，因为最坏情况下，所有数字都相同（比如3500个9），则我们对于每一个$k=j$的情形都需要进行$\mathcal{O}(N)$时间的比较。

如何优化比较呢？这里，我们可以进行一次预处理的动态规划来加速比较。

令$c[i][j]$表示第一个串从$i$开始，第二个串从$j$开始，且满足第一个串不大于第二个串的最长长度。显然$c[i][j]$可以由$c[i+1][j+1]$转移得到。

求得$c[i][j]$之后，我们在进行比较时就只需要判断$c[i-2j][i-j]\ge j$是否成立即可。

• 时间复杂度$\mathcal{O}(|S|^2)$。
• 空间复杂度$\mathcal{O}(|S|^2)$。

参考代码（C++）

using ll = long long;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int numberOfCombinations(string num) {
        if (num[0] == '0')
            return 0;
        
        int n = num.size();
        vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
        dp[1] = vector<ll>(n + 1, 1);
        dp[1][0] = 0;
        
        vector<vector<int>> c(n, vector<int>(n));
        for (int len = 1; len <= n; ++len)
            for (int i = n - 1 - len; i >= 0; --i) {
                if (num[i] < num[i + len])
                    c[i][i + len] = n - i - len;
                else if (num[i] == num[i + len]) {
                    if (i + len == n - 1)
                        c[i][i + len] = 1;
                    else
                        c[i][i + len] = c[i + 1][i + len + 1] + 1;
                }
            }
        
        auto cmp = [&](int l, int r, int len) {
            if (l < 0)
                return false;
            return c[l][r] >= len;
        };
        
        for (int i = 2; i <= n; ++i) {
            dp[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                if (num[i - j] == '0')
                    continue;
                if (cmp(i - 2 * j, i - j, j))
                    dp[i][j] = (dp[i][j] + dp[i - j][j]) % MOD;
                else
                    dp[i][j] = (dp[i][j] + dp[i - j][j - 1]) % MOD;   
            }
            for (int j = 1; j <= n; ++j)
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
        }
        
        return dp[n][n];
    }
};

统计信息

通过次数	提交次数	AC比率
821	3236	25.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言