# 1416.Restore-The-Array

## 1416. Restore The Array

## 题目地址

<https://leetcode.com/problems/restore-the-array/>

## 题目描述

```
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 1:
Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:
Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:
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]

Example 4:
Input: s = "2020", k = 30
Output: 1
Explanation: The only possible array is [20,20]. [2020] is invalid because 2020 > 30. [2,020] is ivalid because 020 contains leading zeros.

Example 5:
Input: s = "1234567890", k = 90
Output: 34

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

## 代码

### Approach #1 DFS

Time: `O(n * log10(k))` && Space: O(n)

Explain: There are total `n` states, each state needs maximum `log10(k)` iteration loops to calculate the result.

```java
class Solution {
    public int numberOfArrays(String s, int k) {
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return dfs(s, k, memo, 0);
    }

    private int dfs(String s, int k, int[] memo, int i) {
        if (i == s.length()) return 1;
        if (s.charAt(i) == '0') return 0;
        if (memo[i] != -1)   return memo[i];

        int ans = 0;
        long num = 0;
        for (int j = i; j < s.length(); j++) {
            num = num * 10 + s.charAt(j) - '0';
            if (num > k) break;
            ans += dfs(s, k, memo, j + 1);
            ans %= 1000_000_007;
        }

        memo[i] = ans;
        return ans;
    }
}
```

### Approach #2 DP

Time: `O(n log k)` Space: `O(n)`

```java
class Solution {
    int mod = (int)1e9 + 7;
    public int numberOfArrays(String s, int k) {
        if (s == null || s.length() == 0)     return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1; // initial 
        for (int i = n - 1; i >= 0; i--) {
            long num = s.charAt(i) - '0'; // long
            if (num != 0) {
                for (int j = i + 1; j <= n; j++) {
                    if (num > k)    break;
                    dp[i] = (dp[i] + dp[j]) % mod;
                    if (j < n) {
                        num = num * 10 + s.charAt(j) - '0';
                    }
                }
            } else {
                dp[i] = 0;
            }
        }

        return dp[0];
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/1416.restore-the-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.