Restore The Array

You can utilize dynamic programming to solve this problem. Here’s the code that returns the number of possible arrays:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1

        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue

            num = 0
            for j in range(i, n):
                num = num * 10 + int(s[j])
                if num > k:
                    break
                dp[i] += dp[j + 1]
                dp[i] %= MOD

        return dp[0]

This code applies dynamic programming from right to left, considering the possible integers that could be in the range [1, k]. It returns the total number of arrays that can be printed as s, modulo 10^9 + 7.

Here’s how the code works:

• dp[i] stores the number of ways to print the substring s[i:].
• If a character is ‘0’, we skip it, as no integer can start with 0.
• We loop through the string and form numbers, checking if they are in the range [1, k].
• We update dp[i] based on the value of dp[j + 1], where j is the current position in the inner loop.

The final result is stored in dp[0], which considers the entire string.