Hard

题目描述

你在一个名为 num 的字符串中写下了许多正整数。但是，你意识到你忘记添加逗号来分隔不同的数字。你记得整数列表是非递减的，并且没有整数有前导零。

返回你可能写下的整数列表的方案数，以得到字符串 num。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：num = "327"
输出：2
解释：你可能写下了以下数字：
3, 27
327

示例 2：

输入：num = "094"
输出：0
解释：没有数字可以有前导零，并且所有数字必须是正数。

示例 3：

输入：num = "0"
输出：0
解释：没有数字可以有前导零，并且所有数字必须是正数。

约束条件：

  • 1 <= num.length <= 3500
  • num 由数字 ‘0’ 到 ‘9’ 组成

解题思路

这道题需要用动态规划来解决。核心思路是：对于字符串的每个位置，考虑以该位置结尾的所有可能数字的分割方案。

状态定义：

  • dp[i][j] 表示以位置 i 结尾，最后一个数字长度为 j 的分割方案数

状态转移：

  1. 如果当前数字有前导零（且长度>1），则方案数为0
  2. 否则，需要枚举上一个数字的所有可能长度
  3. 上一个数字的长度不能超过当前数字的长度（保证非递减）
  4. 当长度相等时，需要比较数值大小

优化技巧：

  1. 使用前缀和优化状态转移，避免重复计算
  2. 预处理字符串比较，快速判断两个子串的大小关系
  3. 使用滚动数组优化空间复杂度

关键点：

  • 处理前导零的特殊情况
  • 高效比较两个数字字符串的大小
  • 利用前缀和加速DP转移过程

时间复杂度主要来自于预处理和DP转移，通过合理的优化可以在限定时间内通过。

代码实现

class Solution {
public:
    int numberOfCombinations(string num) {
        int n = num.length();
        const int MOD = 1e9 + 7;
        
        if (num[0] == '0') return 0;
        
        // 预处理：计算LCP (Longest Common Prefix)
        vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (num[i] == num[j]) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                } else {
                    lcp[i][j] = 0;
                }
            }
        }
        
        // 比较两个子串的大小
        auto compare = [&](int i1, int j1, int i2, int j2) -> bool {
            int len1 = j1 - i1 + 1, len2 = j2 - i2 + 1;
            if (len1 != len2) return len1 < len2;
            int common = lcp[i1][i2];
            if (common >= len1) return false; // 相等
            return num[i1 + common] < num[i2 + common];
        };
        
        // dp[i][j] 表示以位置i结尾，最后一个数字长度为j的方案数
        vector<vector<long long>> dp(n, vector<long long>(n + 1, 0));
        vector<long long> prefix(n + 1, 0);
        
        // 初始化
        for (int j = 1; j <= n; j++) {
            if (j == 1 || num[0] != '0') {
                dp[j - 1][j] = 1;
            }
        }
        
        for (int i = 0; i < n; i++) {
            prefix[0] = 0;
            for (int j = 1; j <= n; j++) {
                prefix[j] = (prefix[j - 1] + dp[i][j]) % MOD;
            }
            
            for (int j = 1; j <= n - i - 1; j++) {
                int start = i + 1;
                int end = start + j - 1;
                if (end >= n || (j > 1 && num[start] == '0')) continue;
                
                // 找到最大的长度k，使得前面的数字不超过当前数字
                int maxK = j;
                for (int k = 1; k <= min(j, i + 1); k++) {
                    int prevStart = start - k;
                    if (prevStart < 0) break;
                    if (k < j || compare(prevStart, start - 1, start, end)) {
                        dp[end][j] = (dp[end][j] + dp[start - 1][k]) % MOD;
                    } else if (k == j) {
                        // 长度相等且前面的数不小于当前数，只能取相等的情况
                        if (!compare(start, end, prevStart, start - 1)) {
                            dp[end][j] = (dp[end][j] + dp[start - 1][k]) % MOD;
                        }
                        break;
                    }
                }
            }
        }
        
        long long result = 0;
        for (int j = 1; j <= n; j++) {
            result = (result + dp[n - 1][j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        n = len(num)
        MOD = 10**9 + 7
        
        if num[0] == '0':
            return 0
        
        # 预处理：计算LCP (Longest Common Prefix)
        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] = lcp[i + 1][j + 1] + 1
        
        def compare(i1, j1, i2, j2):
            # 比较 num[i1:j1+1] 和 num[i2:j2+1]
            len1, len2 = j1 - i1 + 1, j2 - i2 + 1
            if len1 != len2:
                return len1 < len2
            common = lcp[i1][i2]
            if common >= len1:
                return False  # 相等
            return num[i1 + common] < num[i2 + common]
        
        # dp[i][j] 表示以位置i结尾，最后一个数字长度为j的方案数
        dp = [[0] * (n + 1) for _ in range(n)]
        
        # 初始化
        for j in range(1, n + 1):
            if j == 1 or num[0] != '0':
                if j <= n:
                    dp[j - 1][j] = 1
        
        for i in range(n):
            for j in range(1, n - i):
                start = i + 1
                end = start + j - 1
                if end >= n or (j > 1 and num[start] == '0'):
                    continue
                
                for k in range(1, min(j + 1, i + 2)):
                    prev_start = start - k
                    if prev_start < 0:
                        break
                    
                    if k < j or compare(prev_start, start - 1, start, end):
                        dp[end][j] = (dp[end][j] + dp[start - 1][k]) % MOD
                    elif k == j and not compare(start, end, prev_start, start - 1):
                        dp[end][j] = (dp[end][j] + dp[start - 1][k]) % MOD
        
        return sum(dp[n - 1]) % MOD

public class Solution {
    public int NumberOfCombinations(string num) {
        int n = num.Length;
        const int MOD = 1000000007;
        
        if (num[0] == '0') return 0;
        
        // 预处理：计算LCP (Longest Common Prefix)
        int[,] lcp = new int[n + 1, n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (num[i] == num[j]) {
                    lcp[i, j] = lcp[i + 1, j + 1] + 1;
                }
            }
        }
        
        bool Compare(int i1, int j1, int i2, int j2) {
            int len1 = j1 - i1 + 1, len2 = j2 - i2 + 1;
            if (len1 != len2) return len1 < len2;
            int common = lcp[i1, i2];
            if (common >= len1) return false;
            return num[i1 + common] < num[i2 + common];
        }
        
        // dp[i,j] 表示以位置i结尾，最后一个数字长度为j的方案数
        long[,] dp = new long[n, n + 1];
        
        // 初始化
        for (int j = 1; j <= n; j++) {
            if (j == 1 || num[0] != '0') {
                if (j <= n) {
                    dp[j - 1, j] = 1;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= n - i - 1; j++) {
                int start = i + 1;
                int end = start + j - 1;
                if (end >= n || (j > 1 && num[start] == '0')) continue;
                
                for (int k = 1; k <= Math.Min(j, i + 1); k++) {
                    int prevStart = start - k;
                    if (prevStart < 0) break;
                    
                    if (k < j || Compare(prevStart, start - 1, start, end)) {
                        dp[end, j] = (dp[end, j] + dp[start - 1, k]) % MOD;
                    } else if (k == j && !Compare(start, end, prevStart, start - 1)) {
                        dp[end, j] = (dp[end, j] + dp[start - 1, k]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        for (int j = 1; j <= n; j++) {
            result = (result + dp[n - 1, j]) % MOD;
        }
        
        return (int)result;
    }
}

var numberOfCombinations = function(num) {
    const n = num.length;
    const MOD = 1e9 + 7;
    
    if (num[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大O表示法说明
时间复杂度O(n³)预处理LCP需要O(n²)，DP转移需要O(n³)

相关题目