1416. 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 s 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, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 109 + 7.

class Solution {
    int dp[100001], mod = 1e9 + 7;
    int helper(string& s, int p, int k) {
        if(p == s.length()) return 1;
        if(dp[p] != -1) return dp[p];
        if(s[p] == '0') return 0;
        long now = 0;
        int& res = dp[p] = 0;
        for(int i = p; i < s.length(); i++) {
            now = now * 10 + (s[i] - '0');
            if(now > k) break;
            res = (res + helper(s, i + 1, k)) % mod;
        }
        return res;
    }
public:
    int numberOfArrays(string s, int k) {
        memset(dp, -1, sizeof dp);
        return helper(s, 0, k);
    }
};