Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1517. Restore The Array

My accepted Python solution to LeetCode problem 1517, Restore The Array, running in 719ms.

  • Difficulty: Hard
  • Python
  • Runtime 719ms
  • Memory 20.6MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 719ms, memory 20.6MB, accepted 2025-12-29.

python
class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        k_len = len(str(k))
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            for j in range(max(0, i - k_len), i):
                # Check substring s[j:i]
                if s[j] == '0':  # No leading zeros
                    continue
                sub = s[j:i]
                # Compare as strings if same length, otherwise by length
                if len(sub) < k_len or (len(sub) == k_len and sub <= str(k)):
                    dp[i] = (dp[i] + dp[j]) % MOD
        
        return dp[n]

Source