---

1416. 恢复数组

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 1416. 恢复数组 - 力扣

题目大意

描述：给定一个字符串 $s$ 和一个整数 $k$。将 $s$ 分割成若干非空子串，每个子串表示的整数在 $[1, k]$ 范围内，且没有前导零。

要求：返回分割方案数。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le s.length \le 10^5$。
• $1 \le k \le 10^9$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：DP

1. 核心思想

定义 $dp[i]$ 表示前 $i$ 个字符（$s[0 \dots i-1]$）的分割方案数。

转移：枚举最后一个子串的起点 $j$（从 $i-1$ 向前），$s[j \dots i-1]$ 形成的整数 $\le k$，且无前导零。$dp[i] += dp[j]$。

2. 具体步骤

第 1 步：初始化 $dp[0] = 1$。

第 2 步：遍历 $i = 1 \to n$：

• 从 $i-1$ 开始向前枚举 $j$，如果 $s[j] == '0'$（前导零），跳过。
• 截取 $num = int(s[j:i])$。
• 如果 $num > k$，由于 $s$ 长度很大但 $k$ 有限，且数字增长很快，可以提前终止（因为子串长度超过 $k$ 位数时一定 $> k$）。
• 否则 $dp[i] = (dp[i] + dp[j]) \mod MOD$。

第 3 步：返回 $dp[n]$。

3. 复杂度优化

$k \le 10^9$，其十进制位数最多 $10$ 位。所以 $j$ 只需要向前枚举最多 $10$ 位即可。因此时间 $O(n \times 10) = O(n)$。

4. 举例说明

以 $s = "1000", k = 10000$ 为例：

$dp[0] = 1$

• $i=1$：$s[0:1]="1"$，$\le k$，$dp[1] += dp[0] = 1$。
• $i=2$：$s[1:2]="0"$（前导零），跳过。$s[0:2]="10"$，$\le k$，$dp[2] += dp[0] = 1$。
• $i=3$：$s[2:3]="0"$，跳过。$s[1:3]="00"$，前导零。$s[0:3]="100"$，$\le k$，$dp[3] += dp[0] = 1$。
• $i=4$：$s[3:4]="0"$，跳过。$s[2:4]="00"$，跳过。$s[1:4]="000"$，前导零。$s[0:4]="1000"$，$\le k$，$dp[4] += dp[0] = 1$。

结果：$1$（只有一种分法："1000"）。

思路 1：代码

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        max_len = len(str(k))  # k 的十进制位数

        for i in range(1, n + 1):
            # 最多检查 max_len 位
            for j in range(max(0, i - max_len), i):
                if s[j] == '0':
                    continue
                num = int(s[j:i])
                if num > k:
                    continue
                dp[i] = (dp[i] + dp[j]) % MOD

        return dp[n]

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log_{10} k)$，$k \le 10^9$，$\log_{10} k \le 10$，相当于 $O(n)$。
• 空间复杂度：$O(n)$，DP 数组。