Description

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.
Given the string s and the integer k. There can be multiple ways to restore the array.
Return the number of possible array that can be printed as a string s using the mentioned program.
The number of ways could be very large so return it modulo 10^9 + 7

Example

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

Note

1 <= s.length <= 10^5.
s consists of only digits and doesn't contain leading zeros.
1 <= k <= 10^9.

分析

和 decode words 很像，有实现上的难点（在代码实现会标出那个地方有点难想）

code

class Solution(object):
    def numberOfArrays(self, num, k):

        n = len(str(k))
        dp = [0]*(len(num) + n)
        
        def oord(i):
            return ord(i) - ord('0')

        def vp(i):
            return oord(num[i])
        
        if k >= vp(len(num)-1) and vp(len(num)-1) != 0:
            dp[len(num)-1] = 1
        
        for i in reversed(range(0, len(num)-1)):
            if num[i] == '0':
                continue
            for j in range(1+i, min(n+i, len(num))):
                if num[j] == '0':
                    continue
                if k >= int(num[i:j]):
                    dp[i] += dp[j]
                dp[i] %= 1000000007

            if k >= int(num[i:min(n+i, len(num))]):             # 用这个处理 end 部分的数据有点难想～（可能只是折磨我好久吧。对算法大佬来说，这就是小 case ！）
                if min(n+i, len(num)) == len(num):
                    dp[i] += 1
                else:
                    dp[i] += dp[min(n+i,len(num))]
            dp[i] %= 1000000007
                
        return dp[0]%1000000007

总结

Runtime: 2132 ms, faster than 62.38% of Python online submissions for Restore The Array.
Memory Usage: 19.6 MB, less than 54.44% of Python online submissions for Restore The Array.