Участник:Nik7/Restore The Array

Материал из DISCOPAL
Перейти к: навигация, поиск

«Restore The Array»

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        modulo = 1_000_000_007
        log10k = len(str(k))
        dp = [0] * len(s)
        for i in range(len(s)):
            for j in range(i, -1, -1):
                if i - j + 1 > log10k:
                    break
                if s[j] == '0':
                    continue
                if int(s[j:i+1]) > k:
                    break
                dp[i] += dp[j-1] if j-1 >= 0 else 1
                dp[i] %= modulo
        return dp[-1]