LeetCode 1416: Restore The Array

Explanation:

To solve this problem, we can use dynamic programming. We can define a recursive function that calculates the number of valid arrays for a given string and index. We will iterate over the string, considering different split points and recursively calling the function for the remaining parts of the string. We will keep track of the valid arrays using a dynamic programming array.

• Initialize a dynamic programming array to store the number of valid arrays for each index in the string.
• Define a recursive function that calculates the number of valid arrays for a given string and index. The function should consider different split points and recursively call itself for the remaining parts of the string.
• Use dynamic programming to avoid recalculating the same subproblems.
• Return the number of valid arrays for the entire string.

Time complexity: O(n), where n is the length of the input string s. Space complexity: O(n), for the dynamic programming array.

class Solution {
    public int numberOfArrays(String s, int k) {
        int MOD = 1000000007;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') continue;
            long num = 0;
            dp[i] = 0;
            for (int j = i; j < n; j++) {
                num = num * 10 + (s.charAt(j) - '0');
                if (num > k) break;
                dp[i] = (dp[i] + dp[j + 1]) % MOD;
            }
        }
        
        return dp[0];
    }
}