LeetCode 题解工作台
恢复数组
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [1, k] 之间，且数组中的数字都没有前导 0 。 给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。 按照上述程序，请你返回所有可能输出字符串 s 的数组方…
2
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串，我们所知道的信息只有：数组中所有整数都在 [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.
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * log10(k)) because for each index, we can consider substrings up to the length of k's digits. Space complexity is O(n) for the dp array. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check for substrings that start with '0' to avoid invalid numbers.
- question_mark
Consider the maximum number of digits that k allows to optimize substring checks.
- question_mark
Ask candidates to explain how dp[i] builds upon dp[j] for later indices.
常见陷阱
外企场景- error
Forgetting to skip substrings with leading zeros.
- error
Not limiting substring length to the number of digits in k, causing unnecessary iterations.
- error
Incorrect modulo usage leading to integer overflow.
进阶变体
外企场景- arrow_right_alt
Count the number of arrays if numbers could include zero but still within [0, k].
- arrow_right_alt
Find the lexicographically smallest valid array instead of counting.
- arrow_right_alt
Return all valid arrays instead of just the count, emphasizing reconstruction from dp.