Hard

题目描述

一个程序原本应该打印一个整数数组。但是这个程序忘记打印空格了，于是数组被打印成了一个数字字符串 s。我们只知道数组中所有整数都在范围 [1, k] 内，并且数组中没有前导零。

给定字符串 s 和整数 k，返回可能被打印成 s 的数组的数量。由于答案可能很大，请返回答案对 10^9 + 7 取模的结果。

示例 1：

输入：s = "1000", k = 10000
输出：1
解释：唯一可能的数组是 [1000]

示例 2：

输入：s = "1000", k = 10
输出：0
解释：不存在符合条件的数组，因为所有整数都必须 >= 1 且 <= 10

示例 3：

输入：s = "1317", k = 2000
输出：8
解释：可能的数组有 [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

约束条件：

  • 1 <= s.length <= 10^5
  • s 只包含数字且不包含前导零
  • 1 <= k <= 10^9

解题思路

这是一个经典的动态规划问题，需要考虑如何将字符串分割成合法的数字。

思路分析：

我们可以使用动态规划来解决这个问题。定义 dp[i] 表示从字符串位置 i 开始到结尾能够构成的合法数组的数量。

状态转移的关键在于：对于位置 i，我们需要尝试所有可能的数字分割。从位置 i 开始，我们可以取 1 位、2 位、3 位…直到不超过字符串长度的数字，但有以下约束：

  1. 取出的数字不能有前导零（除非是单独的 “0”，但题目说明不包含前导零）
  2. 取出的数字必须 ≤ k
  3. 取出的数字必须 ≥ 1

状态转移方程为：dp[i] = sum(dp[i+len]) 其中 len 是从位置 i 开始取的合法数字的长度。

边界条件：dp[n] = 1（字符串末尾后一个位置，表示成功分割完成）

为了优化比较操作，我们可以先将 k 转换为字符串，这样在比较数字大小时更加高效。

时间复杂度主要取决于每个位置需要尝试的数字长度，最坏情况下需要尝试到 k 的位数长度。

代码实现

class Solution {
public:
    int numberOfArrays(string s, int k) {
        int n = s.length();
        vector<int> dp(n + 1, 0);
        dp[n] = 1;
        string k_str = to_string(k);
        const int MOD = 1e9 + 7;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') continue;
            
            for (int j = i; j < n; j++) {
                string num = s.substr(i, j - i + 1);
                if (num.length() > k_str.length() || 
                    (num.length() == k_str.length() && num > k_str)) {
                    break;
                }
                dp[i] = (dp[i] + dp[j + 1]) % MOD;
            }
        }
        
        return dp[0];
    }
};

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1
        k_str = str(k)
        MOD = 10**9 + 7
        
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue
                
            for j in range(i, n):
                num = s[i:j+1]
                if len(num) > len(k_str) or (len(num) == len(k_str) and num > k_str):
                    break
                dp[i] = (dp[i] + dp[j + 1]) % MOD
                
        return dp[0]

public class Solution {
    public int NumberOfArrays(string s, int k) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        dp[n] = 1;
        string kStr = k.ToString();
        const int MOD = 1000000007;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') continue;
            
            for (int j = i; j < n; j++) {
                string num = s.Substring(i, j - i + 1);
                if (num.Length > kStr.Length || 
                    (num.Length == kStr.Length && string.Compare(num, kStr) > 0)) {
                    break;
                }
                dp[i] = (dp[i] + dp[j + 1]) % MOD;
            }
        }
        
        return dp[0];
    }
}

var numberOfArrays = function(s, k) {
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[n] = 1;
    const kStr = k.toString();
    const MOD = 1e9 + 7;
    
    for (let i = n - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大O表示法
时间复杂度O(n × log k)
空间复杂度O(n)

其中 n 是字符串 s 的长度，log k 是数字 k 的位数（即每个位置最多尝试的数字长度）。

相关题目