1416. Restore The Array

题目信息

题号:

1416

难度:

Hard

主题:

字符串、动态规划、计数

原题:

LeetCode 1416

重点:

把数字字符串切分为若干范围 [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] 内,也不能作为合法数组元素。