恢复数组

难度: Hard

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序，请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大，请你返回它对 10^9 + 7 取余后的结果。

示例 1：

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

示例 2：

输入：s = "1000", k = 10
输出：0
解释：不存在任何数组方案满足所有整数都 >= 1 且 <= 10 同时输出结果为 s 。

示例 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]

示例 4：

输入：s = "2020", k = 30
输出：1
解释：唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案，原因是 2020 > 30 。 [2,020] 也不是可行的数组方案，因为 020 含有前导 0 。

示例 5：

输入：s = "1234567890", k = 90
输出：34

提示：

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

Submission

运行时间: 460 ms

内存: 20.3 MB

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

Explain

此题解采用动态规划的方法解决问题。定义 dp[i] 为字符串 s 的前 i 个字符可以形成的有效数组的方案数。初始化 dp[0] = 1，表示空字符串有一种划分方式（即没有数字）。遍历字符串 s 的每一个位置 i，如果当前位置字符为 '0' 或 dp[i] 为 0（表示无法从前面的字符转移至此），则直接跳过该位置。对于每个有效的起点 i，尝试将从位置 i 到 j 的子串转化为数字，并判断是否不超过 k。若不超过 k，则将 dp[i] 的方案数加到 dp[j+1] 上。这样，我们可以通过前面的位置来更新后面的位置的方案数。最终，dp[len(s)] 存储的是整个字符串 s 可以形成的有效数组的总方案数。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        v = [int(c) for c in s] # 将字符串 s 转换为整数列表
        dp = [1] + [0] * len(v) # 初始化 dp 数组，dp[0] = 1 表示空字符串的一种划分方式
        MOD = 10**9 + 7 # 定义模数
        for i in range(len(v)):
            if dp[i] == 0 or v[i] == 0: # 如果当前位置为 '0' 或 dp[i] 为 0 则跳过
                continue
            num = 0
            dp[i] %= MOD # 防止 dp[i] 过大
            for j in range(i, len(v)):
                num = num * 10 + v[j] # 尝试构建一个数字
                if num > k:
                    break
                dp[j + 1] += dp[i] # 更新 dp[j+1] 的状态
        return dp[-1] % MOD # 返回结果，并取模

Explore

在动态规划数组 dp 中，dp[i] 表示的是字符串 s 的前 i 个字符可以形成的有效数组的方案数。具体来说，dp[i] 记录了从字符串开始到第 i 个字符为止，所有可以从 s 中提取并转化为不超过 k 的整数的划分方式的总数。

在该算法中，检查 dp[i] 是否为 0 的目的是为了确定从字符串的开始到第 i 个字符的位置能否形成有效的数字组合。如果 dp[i] 为 0，这意味着没有任何有效的方式可以将 s 的前 i 个字符划分成满足条件的整数序列，因此没有必要继续从这个位置尝试生成新的数字，可以直接跳过以提高效率。

将数字字符转换成整数列表进行处理主要是为了方便和效率。使用整数列表可以直接进行数字的相加和乘法操作，这在构建数字和进行比较时更为直观和快速。如果直接使用字符串，每次构造新数字或比较大小时都需要进行字符串到数字的转换，这会增加处理时间和复杂度。

在内层循环中，由于 num 是通过连续地将数字追加到已有的数值后面（即 num = num * 10 + v[j]）来构建的，这确实有可能导致整数溢出，特别是当 s 很长或数值 k 很大时。为了避免这种情况，算法中加入了一个检查点：一旦 num 超过了 k，就会立即终止内层循环。这样，不仅避免了不必要的计算，也防止了 num 增长到可能导致溢出的大小。