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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        

Solutions:
class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		dp = [-1] * len(s)
		return self.dfs(s, k, 0, dp)

	def dfs(self, s: str, k: int, start: int, dp: List[int]) -> int:
		if start == len(s):
			return 1
		if s[start] == '0':
			return 0
		if dp[start] != -1:
			return dp[start]
		(res, num) = (0, 0)
		for i in range(start, len(s)):
			num = num * 10 + (ord(s[i]) - ord('0'))
			if num > k:
				break
			res += self.dfs(s, k, i + 1, dp)
			res %= 10 ** 9 + 7
		dp[start] = res
		return res


class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		n = len(s)
		b = ord('0')
		MOD = 10 ** 9 + 7
		dp = collections.deque([0] * 10)
		dp[0] = 1
		for i in range(n - 1, -1, -1):
			if s[i] == '0':
				dp.pop()
				dp.appendleft(0)
				continue
			num = 0
			cnt = 0
			for j in range(i, n):
				num = num * 10 + ord(s[j]) - b
				if num <= k:
					cnt += dp[j - i] % MOD
				else:
					break
			dp.appendleft(cnt % MOD)
			dp.pop()
		return dp[0]


class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		MOD = 10 ** 9 + 7
		n = len(s)

		@lru_cache(None)
		def dp(i):
			if i == n:
				return 1
			if s[i] == '0':
				return 0
			num = 0
			ans = 0
			for j in range(i, n):
				num = num * 10 + ord(s[j]) - ord('0')
				if num > k:
					break
				ans += dp(j + 1)
			return ans % MOD
		return dp(0)


class Solution:

	def numberOfArrays(self, S: str, K: int) -> int:
		import sys
		sys.setrecursionlimit(10 ** 9 + 7)

		@lru_cache(None)
		def ways(idx):
			if idx == len(S):
				return 1
			if S[idx] == '0':
				return 0
			ans = 0
			num = 0
			for i in range(idx, len(S)):
				num = num * 10 + (ord(S[i]) - ord('0'))
				if num > K:
					break
				ans = (ans + ways(i + 1)) % 1000000007
			return ans
		return ways(0)


class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		n = len(s)
		b = ord('0')
		MOD = 10 ** 9 + 7

		@lru_cache(None)
		def dp(i):
			if i == n:
				return 1
			if s[i] == '0':
				return 0
			cnt = 0
			num = ord(s[i]) - b
			while num <= k:
				cnt += dp(i + 1) % MOD
				i += 1
				if i < n:
					num = num * 10 + ord(s[i]) - b
				else:
					break
			return cnt % MOD
		return dp(0)


class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		cache = {}
		n = len(s)
		mod = 10 ** 9 + 7

		def process(i):
			if i == n:
				return 1
			elif s[i] == '0':
				return 0
			else:
				if not i in cache:
					ans = 0
					x = 0
					j = 0
					while i + j < n:
						x = x * 10 + (ord(s[i + j]) - 48)
						if x <= k:
							ans += process(i + j + 1)
							j += 1
						else:
							break
					cache[i] = ans % mod
				return cache[i]
		return process(0)


MOD = int(1000000000.0 + 7)

class Solution:

	def numberOfArrays(self, s: str, k: int) -> int:
		dp = [-1 for _ in s]
		n = len(s)

		def recurse(i: int) -> int:
			if i == n:
				return 1
			if dp[i] != -1:
				return dp[i]
			result = 0
			val = 0
			for j in range(i, n):
				val = 10 * val + (ord(s[j]) - ord('0'))
				if val > k:
					break
				elif j == n - 1 or s[j + 1] != '0':
					result = (result + recurse(j + 1)) % MOD
			dp[i] = result
			return result
		return recurse(0)