1416. Restore The Array¶
题目信息¶
- 题号:
1416
- 难度:
Hard
- 主题:
字符串、动态规划、计数
- 原题:
- 重点:
把数字字符串切分为若干范围
[1,k]内且无前导零的整数;统计不同切分方式并取模
题目重述¶
给定只包含数字的字符串 s 和正整数 k。需要把 s 切分成若干连续非空片段,每个片段解释为一个十进制整数。
每个整数必须位于 [1,k],并且不能含前导零。请返回合法切分方案数量对 10^9 + 7 取模后的结果。
1 <= s.length <= 10^5,1 <= k <= 10^9。
自建示例¶
不同切分边界可以得到多个合法数组:
输入:s = "123", k = 12
输出:2
解释:合法切分为 [1,2,3] 和 [12,3];片段 23 超过 k。
以零开始的片段非法:
输入:s = "0", k = 10
输出:0
解释:零不在允许范围 [1,10] 内,也不能作为合法数组元素。